Introduction
Both merge sort and quick sort are popular sorting algorithms. They both use recursion and leverage devide and conquer principles. But what are their differences?
Time Complexity
Merge sort has time complexity as O(nlogn), where n is the size of the array to be sorted. Quick sort has average time complexity as O(nlogn). For the worst case, quick sort algorithm’s time complexity can be O(n^2). For example, if the array is already sorted in ascending order and we pick first element as pivot, every time we partition array into 2 subarrays with size 1 and n - 1, thus the time complexity can be O(n^2). However, for merge sort, it’s time complexity will be constantly O(nlogn).
Space Complexity
Without considering the call stack trace, quick sort is sorting numbers in-place, so only O(1) space complexity. However, merge sort needs an extra array for sorting and merging back numbers, so it needs O(n) space.
Stability
Let’s say we have 2 equal numbers, after sorting, can they still remain the relative order as in original array? If yes, we say this algorithm has high stability. Apperantly, merge sort can gurantee the relative order, but not quick sort. Thus we say, merge sort has better stability than quick sort.
Divide and Conquer
Both quick sort and merge sort leverage the principle of divide and conquer. The difference is: quick sort first “globally” order the array, and then “locally” order each subarrays. Merge sort is in opposite way: first “locally” order the subarray, and then “globally” order the array.