Quick Sort
In Arrays.sort(int[] a) of Java, it use the Dual-pivot Quick Sort algorithm:
One-pivot Quick Sort
Quick Sort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quick sort that pick pivot in different ways:
- Always pick first element as pivot.
- Always pick last element as pivot (implemented below)
- Pick a random element as pivot.
- Pick median as pivot.
1 |
|
It’s an unstable and in-place sort algorithm, the time complexity can be expressed as the recurrence relation: $T(n) = T(k) + T(n-k-1) + n$
- In worst case, we get extremely unbalanced array after each partition: $T(n) = T(0) + T(n-1) + n = T(n-1) + n = n * (n + 1) /2 \approx O(n^2)$
- In best case, we get equally partitioned array each time: \(T(n) = 2*T(n/2)+n = 2*(T(n/4)+n/2)+n = 2*(2*(T(n/8)+n/4)+n/2)+n = 2^k*T(n/2^k)+k*n\) When $k = \log_2 n, T(n/2^k) = T(1), T(n) = C*n + n * \log_2 n \approx O(n \log n)$
- In general case, we can suppose the partition puts O(n/9) elements in one set and O(9n/10) elements in other set: $T(n) = T(n/9) + T(n/10) + n \approx O(n \log n)$
Dual-pivot Quick Sort
The idea of dual pivot quick sort is to take two pivots, one in the left end of the array and the second, in the right end of the array. The left pivot must be less than or equal to the right pivot, so we swap them if necessary.
Then, we begin partitioning the array into three parts: in the first part, all elements will be less than the left pivot, in the second part all elements will be greater or equal to the left pivot and also will be less than or equal to the right pivot, and in the third part all elements will be greater than the right pivot. Then, we shift the two pivots to their appropriate positions as we see in the below bar, and after that we begin quick sorting these three parts recursively, using this method.
Dual pivot quick sort is a little bit faster than the original single pivot quicksort. But still, the worst case will remain $O(n^2)$ when the array is already sorted in an increasing or decreasing order.
Merge Sort
In Arrays.sort(Object[] a) of Java, it use the Merge Sort algorithm. Like QuickSort, Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.
1 |
|
It’s a stable but not in-place sort algorithm, the time complexity can be expressed as following recurrence relation in best, worst, average cases:
\(T(n) = 2*T(n/2)+n = 2*(T(n/4)+n/2)+n = 2*(2*(T(n/8)+n/4)+n/2)+n = 2^k*T(n/2^k)+k*n\) The space complexity is O(n), but in case of sorting linked list, the space complexity is O(1):
1 |
|