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
|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.|
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, A, A,…….., A[n] of n number which have to be sorted. The quick sort algorithm comprised of the following steps.
- The first element or any random element selected as the key, assume key = A(1).
- 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;
- Consistently, increment the “low” pointer by one position until (A[low]>key).
- Constantly, decrement the “up” pointer by one position until (A[up]<=key).
- If up is greater than low interchange A[low] with A[up].
- 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.
- 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.
- 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, A, ………, A[n]. The merge sort follows the given steps.
- Split the array A into approximately n/2 sorted sub-array by 2, which means that the elements in the (A, A), (A, A), (A[k],A[k+1]), (A[n-1], A[n]) sub-arrays must be in sorted order.
- 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, A, A, A),……,(A[k-1], A[k], A[k+1], A[k+2]),……., (A[n-3], A[n-2], A[n-1], A[n]).
- 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.
Key Differences Between Quick Sort and Merge Sort
- In the merge sort, the array must be parted into just two halves (i.e. n/2). As against, in quick sort, there is no compulsion of dividing the list into equal elements.
- The worst case complexity of quick sort is O(n2) as it takes a lot more comparisons in the worst condition. In contrast, merge sort have the same worst case and average case complexities, that is O(n log n).
- Merge sort can operate well on any type of data sets whether it is large or small. On the contrary, the quick sort cannot work well with large datasets.
- Quick sort is faster than merge sort in some cases such as for small data sets.
- Merge sort requires additional memory space to store the auxiliary arrays. On the other hand, the quick sort doesn’t require much space for extra storage.
- Merge sort is more efficient than quick sort.
- The quick sort is internal sorting method where the data that is to be sorted is adjusted at a time in main memory. Conversely, the merge sort is external sorting method in which the data that is to be sorted cannot be accommodated in the memory at the same time and some has to be kept in the auxiliary memory.
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).