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()

Merge()

Merge Sort Example

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

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.