Difference Between Quick Sort and Merge Sort

The quick sort and merge sort algorithms are based on the divide and conquer algorithm which works in the quite similar way. The prior difference between the quick and merge sort is that in quick sort the pivot element is used for the sorting. On the other hand, merge sort does not use pivot element for performing the sorting.

Both sorting techniques, quick sort and merge sort are built on the divide and conquer method in which the set of elements are parted and then combined after rearrangement. The quick sort usually requires more comparisons than merge sort for sorting a large set of elements.

Content: Quick Sort Vs Merge Sort

1. 1. Comparison Chart
   2. Definition
   3. Key Differences
   4. Conclusion

Comparison Chart

Basis for comparison	Quick sort	Merge sort
Partitioning of the elements in the array	The splitting of a list of elements is not necessarily divided into half.	Array is always divided into half (n/2).
Worst case complexity	O(n2)	O(n log n)
Works well on	Smaller array	Operates fine in any type of array.
Speed	Faster than other sorting algorithms for small data set.	Consistent speed in all type of data sets.
Additional storage space requirement	Less	More
Efficiency	Inefficient for larger arrays.	More efficient.
Sorting method	Internal	External

Definition of Quick Sort

Quick sort is pervasively used sorting algorithm as it is fast for the short arrays. The set of the elements is divided into parts repeatedly until it is not possible to divide it further. Quick sort is also known as partition exchange sort. It uses a key element (known as the pivot) for partitioning the elements. One partition contains those elements that are smaller than the key element. Another partition contains those elements that are greater than the key element. The elements are sorted recursively.

Suppose A is an array A[1], A[2], A[3],…….., A[n] of n number which have to be sorted. The quick sort algorithm comprised of the following steps.

1. The first element or any random element selected as the key, assume key = A(1).
2. The “low” pointer is placed at the second and “up” pointer is positioned at the last element of the array, i.e. low=2 and up=n;
3. Consistently, increment the “low” pointer by one position until (A[low]>key).
4. Constantly, decrement the “up” pointer by one position until (A[up]<=key).
5. If up is greater than low interchange A[low] with A[up].
6. Repeat the step 3,4, and 5 until the condition in step 5 fails (i.e. up<=low) then interchange A[up] with the key.
7. If the elements left of the key are smaller than the key and the elements right of the key are greater than the key then the array is partitioned into two sub-arrays.
8. The above procedure is repeatedly applied to the subarrays until the entire array is sorted.

Advantages and Disadvantages

It possesses a good average case behaviour. The running time complexity of the quick sort is good that is it is faster than algorithms such as bubble sort, insertion sort and selection sort. However, it is complex and very recursive, that is the reason it is not suitable for large arrays.

Definition of Merge Sort

Merge sort is an external algorithm which is also based on divide and conquer strategy. The elements are split into sub-arrays (n/2) again and again until only one element is left, which significantly decreases the sorting time. It uses additional storage for storing the auxiliary array. Merge sort uses three arrays where two are used for storing each half, and the third one is used to store the final sorted list. Each array is then sorted recursively. At last, the subarrays are merged to make it n element size of the array. The list always divided into just half (n/2) dissimilar to quick sort.

Let A be the array of n number of elements to be sorted A[1], A[2], ………, A[n]. The merge sort follows the given steps.

1. Split the array A into approximately n/2 sorted sub-array by 2, which means that the elements in the (A[1], A[2]), (A[3], A[4]), (A[k],A[k+1]), (A[n-1], A[n]) sub-arrays must be in sorted order.
2. Combine each pair of pairs to obtain the list of sorted subarrays of size 4; the elements in the subarrays are also in sorted order, (A[1], A[2], A[3], A[4]),……,(A[k-1], A[k], A[k+1], A[k+2]),……., (A[n-3], A[n-2], A[n-1], A[n]).
3. The step 2 is repeatedly performed until there is only one sorted array of size n.

Advantages and Disadvantages

The merge sort algorithm performs in the exact same and precise manner regardless of the number of elements involved in the sorting. It works fine even with the large data set. However, it consumes larger part of memory.

Conclusion

The quick sort is faster cases but is inefficient in some situations and also performs a lot of comparisons as compared to merge sort. Although merge sort requires less comparison, it needs an additional memory space of 0(n) for storing the extra array while quick sort needs space of O(log n).