Many languages use this as default sort algorithm. Very optimized algorithm for modern computer architecture.
Quick sort is typically over twice faster as merge sort. It is In-place sort so we need memory allocation and free memory process). There is only swapping in quick sort which are supported by Register hardware. event theoretically merge sort is better. Quick sort access sequentially so more suitable for modern computer compared to randomly accessing merge sort.
Algorithm
merge sort 반대로 bottom up이 아니라 top down으로 recursive sort를 약한 restriction sort
trivially no merge step for combining
Key part is this divide (partition) step
쉽게 설명하면 첫번째 걸로 전체 작은거 큰거 나눈 다음에, 나눠진 거에서 다시 크고 작은거로 나눠가기. 그래서 worst case is bad (partition is around min or max element) but complexity is only when sorted or reverse
Randomized quicksort
Introducing Randomness
If we introduce random pivot, sorted or reversed is not worst case
every recursion, we use each independent pivot selection
Seonglae Cho
