Merge Sort

  1. Merge Sort Algorithm
  2. Merge Sort Example
  3. Merge Sort Algorithm Implementation
  4. Merge Sort Algorithm Complexity

Merge sort is one of the most popular and efficient sorting algorithms. It is based on the principle of the divide and conquer algorithm. It works by dividing the array into two halves repeatedly until we get the array divided into individual elements. An individual element is a sorted array in itself. Merge sort repeatedly merges these small sorted arrays to produce larger sorted subarrays until we get one final sorted array. It is widely used in e-commerce applications.

Merge Sort Algorithm

Top-down merge sort approach starts from the top with the full array and proceeds downwards to individual elements with recursion.

Suppose we have an unsorted array A[] containing n elements.

MergeSort()

  • Take two variables beg & end then store the index of starting element and ending element.
  • Find the middle point of the array to divide it into two halves using the formula mid =(beg+end)/2.
  • Break the array into two parts arr[beg, .... , mid] and arr[mid+1, .... , end].
  • Repeatedly divide the array into subarrays with single elements using recursion.
  • Call the merge function to start building the sorted array.

Merge()

  • Initialize the auxiliary array output to store the sorted output.
  • Initialize 3 pointers i, j & k.

    i points to the beginning of the first subarray beg.
    j points to the beginning of the second subarray mid+1.
    k initialized with beg maintains the current index of sorted array output.

  • Until we reach the end of arr[beg, .... ,mid] or arr[mid+1, .... ,end] subarray, we pick the smaller value among elements at index i &j and insert into output.
  • Pick the remaining elements and insert them into output once one of the arrays is exhausted.
  • Copy output into arr[beg, ... , end].

Merge Sort Example

Suppose we have the array: (5,3,4,2,1,6). We will sort it using the merge sort algorithm.

Action (5,3,4,2,1,6) mergesort(0,5)
divide (5,3,4) (2,1,6) mergesort(0,2) mergesort(3,5)
divide (5,3) (4) (2,1) (6) mergesort(0,1) mergesort(2,2) mergesort(3,4) mergesort(5,5)
divide (5) (3) (4) (2) (1) (6) Array broken to individual elements
merge (3,5) (4) (1,2) (6) merge(0,1) merge(2,2) merge(3,4) merge(5,5)
merge (3,4,5) (1,2,6) merge(0,2) merge(3,5)
merge (1,2,3,4,5,6) merge(0,5)

We get the sorted array - (1 2 3 4 5 6)

Merge Sort Algorithm Implementation

#include<iostream>
using namespace std;

void merge(int arr[], int beg, int mid, int end) {
    int output[end - beg + 1];
    int i = beg, j = mid + 1, k = 0;
    // add smaller of both elements to the output
    while (i <= mid && j <= end) {
        if (arr[i] <= arr[j]) {
            output[k] = arr[i];
            k += 1; i += 1;
        }
        else {
            output[k] = arr[j];
            k += 1; j += 1;
        }
    }
    // remaining elements from first array
    while (i <= mid) {
        output[k] = arr[i];
        k += 1; i += 1;
    }
    // remaining elements from the second array
    while (j <= end) {
        output[k] = arr[j];
        k += 1; j += 1;
    }
    // copy output to the original array
    for (i = beg; i <= end; i += 1) {
        arr[i] = output[i - beg];
    }
    }

    void mergeSort(int arr[], int beg, int end) {

    if (beg < end) {
        int mid = (beg + end) / 2;
        //divide and conquer
        mergeSort(arr, beg, mid);    // divide : first half
        mergeSort(arr, mid + 1, end);  // divide: second half
        merge(arr, beg, mid, end);   // conquer
    }
    }
    int main() {

    int n = 6;
    int arr[6] = {5, 3, 4, 2, 1, 6};
    cout << "Input array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    mergeSort(arr, 0, n - 1); // Sort elements in ascending order
    cout << "Output array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
}

Merge Sort Algorithm Complexity

Time Complexity

  • Average Case

Merge sort is a recursive algorithm. The following recurrence relation gives the time complexity expression for Merge sort.

T(n) = 2T(n/2) + θ(n)

This result of this recurrence relation gives T(n) = nLogn.We can also see it as an array of size n being divided into a maximum of Logn parts, and merging of each part takes O(n) time.

Hence the time complexity is of the order of [Big Theta]: O(nLogn).

  • Worst Case

The worst-case time complexity is [Big O]: O(nLogn).

  • Best Case

The best-case time complexity is [Big Omega]: O(nLogn). It is the same as the worst-case time complexity.

Space Complexity

Space Complexity for Merge Sort algorithm is O(n)because n auxiliary space is required for storing the sorted subarray in the auxiliary array.

Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

Related Article - Sort Algorithm

  • Comb Sort
  • Pancake Sort