Which is better – Merge sort or Quick sort?

Sorting is a process of arranging items systematically. It is very important to deeply understand sorting algorithms as they are frequently asked in technical and coding interviews.

Different Sorting Algorithms

• Selection Sort
• Bubble Sort
• Insertion Sort
• Merge Sort
• Quick Sort
• Counting Sort
• Radix Sort
• Bucket Sort
• Heap Sort
• Shell Sort

In this article, we’ll learn the difference between Merge & Quick Sort, which one is more efficient to use, and why.

What is Merge Sort?

Merge Sort uses the divide and conquer technique. In the divide and conquer technique, we divide the problem into multiple subproblems, solve them individually, and then their results are combined to form a final solution.

Similarly, in Merge Sort, we –

• divide the array into two parts
• get both parts sorted via recursion
• merge the sorted parts

Working

The height of the Merge Sort tree is O(log n). At each recursive call, we divide in half, sequentially. The overall work done at the nodes of depth ‘i’ is O(n). We partition and merge the 2ⁱ sequence of size n/2ⁱ.We make 2ⁱ⁺¹ recursive calls. Thus, the total running time of merge-sort is O(n*log n).

Time complexity:
Best case – O(n*log n)
Average case – O(n*log n)
Worst case – O(n*log n)

Implementation

import java.util.Arrays;

public class MERGESORTING {
    public static void main(String[] args) {
        int[] arr={5,4,3,2,1};
        merge(arr,0, arr.length);
        System.out.println(Arrays.toString(arr));
    }
    static void merge(int[] arr,int start,int end){
        if(end-start==1){
            return;
        }
        int mid=start+(end-start)/2;
        merge(arr,start,mid);
        merge(arr,mid,end);
        mergeSort(arr,start,mid,end);
    }
    static int[] mergeSort(int[] arr,int start,int mid,int end){
        int[] mix=new int[end-start];
        int i=start;
        int j=mid;
        int k=0;
        while(i<mid && j<end){
            if(arr[i]<arr[j]){
                mix[k]=arr[i];
                i++;
            }
            else{
                mix[k]=arr[j];
                j++;
            }
            k++;
        }
        while(i<mid){
            mix[k]=arr[i];
            i++;
            k++;
        }
        while(j<end){
            mix[k]=arr[j];
            j++;
            k++;
        }
        for(int l=0;l< mix.length;l++){
            arr[start+l]=mix[l];
        }
        return arr;
    }
}Code language: Java (java)

Ouput:
[1, 2, 3, 4, 5]Code language: Java (java)

What is Quick Sort?

Quick Sort also follows the divide and conquer technique. Quick Sort picks an element as a pivot. Numbers less than the pivot are put on the left-hand side of the pivot and numbers greater than the pivot are put on the right-hand side of the pivot. After every pass, you’re putting the pivot in the correct position.

Choosing the pivot:

• It can be any random element
• You can select the rightmost or leftmost element as a pivot.
• Median can be selected as a pivot

Working

Here, we are taking the median as the pivot element.

Time complexity:
Worst case – When the pivot is the smallest element all the time, resulting in an unbalanced partition. So, the worst-case complexity is O(n²).
Best case – When the partition is always balanced i.e. pivot is always in the middle. So, the best-case complexity is O(n*log n).
Average case – Quick Sort’s average case time complexity is O(n*log n).

Implementation

import java.util.Arrays;

public class Quick_Sort {
    public static void main(String[] args) {
        int[] nums={5,4,3,2,1};
        sort(nums,0,nums.length-1);
        System.out.println(Arrays.toString(nums));
    }
    static void sort(int[] nums,int low, int high){
        if(low>=high){
            return;
        }
        int s=low;
        int e=high;
        int m=s+(e-s)/2;
        int pivot=nums[m];
        while(s<=e) {

            while (nums[s] < pivot) {
                s++;
            }
            while (nums[e] > pivot) {
                e--;
            }
            if(s<=e){
                int temp=nums[s];
                nums[s]=nums[e];
                nums[e]=temp;
                s++;
                e--;
            }
        }
        //now my pivot is at correct index, sort the two halves now
        sort(nums,low,e);
        sort(nums,s,high);
    }
}
Code language: Java (java)

Output:
[1, 2, 3, 4, 5]Code language: Java (java)

Difference between Merge and Quick Sorting

Quick Sort	Merge Sort
The array is not necessarily divided into half	The array is divided into half
It works well on smaller arrays	It works fine in any type of array
This sorting method is internal	This sorting method is external
The worst-case complexity is O(n2)	The worst-case complexity is O(n*log n)
It is not stable	It is stable
It is preferred for Arrays	It is preferred for Linked Lists

Merge Sort or Quick Sort

Now that we’ve learned about Merge and Quick Sort and their differences, it’s time to judge which one is better and why.

Despite the complexity of both algorithms being the same, most people prefer to use Quick Sort. This is because:-

• The locality of reference (reading elements in cache) also plays an important role. Quick Sort employs good cache locality which makes it faster than Merge Sort.
• It is easier to avoid the worst case in Quick Sort by just choosing the appropriate element as a pivot
• Quick Sort is in place i.e. no extra memory is required
• Merge Sort takes more space so it is not recommended to use it on large unsorted arrays. Quick Sort is a better option

However, since Quick Sort is an unstable sorting technique, it may change the occurrence of the two similar elements, whereas, Merge Sort is a stable algorithm and doesn’t change the occurrence of the similar elements. Merge Sort is preferred for Linked Lists as it reads the data sequentially.

Conclusion

Both algorithms have their advantages and disadvantages. It depends on the type of data you want to sort. I hope you have understood the concept in detail.

Thanks for reading 🙂