<< Prev : What is heap sort?

What is the difference between Merge Sort and Quick sort?

  • Asked by : Clementine
    December 26th, 2010 15:33
Replies:
1. Merge-Sort and quick sort both follows Divide and Conquer strategy.
2. In worst case, Merge sort still maintains a complexity of O(nlogn) while quick sort becomes O(n^2).
3. In quick sort there is a pivot selection but there is no pivot selection in merge sort. The arrays are partitioned equally which continues recursively and finally its merged.
4. Merge sort is not an inplace sorting while quick sort is.(without regard to the internal stack space that taken by each recursive algorithms).

--Santanu--
  • Replied by : santanu.code@gmail.com
    February 6th, 2012 16:43
Quick sort can be easily made to work in O(nlogn) always by selecting pivot correctly.
For example use median as pivot.

Both Merge-sort and Quick-sort have same average time complexity i.e. O(nlogn). In merge sort the file a[1:n] was divided at its midpoint into sub-arrays which are independently sorted and later merged. Whereas, in quick sort the division into two sub-arrays is made so that the sorted sub-arrays do not need to be merged latter.

To reply to this discussion, please