Merge Sort

Time complexity: O(n log n)

Space complexity: O(n)

Data type: Arrays, Linked Lists

Visualization

Comparisons: 0

Reorders: 0

Delay: 1ms

Items: 50

Definition

Merge Sort is a divide-and-conquer sorting algorithm that recursively splits an array into halves until each subarray contains a single element, then merges them back together in sorted order. The key operation is the merge step, which combines two sorted subarrays into a single sorted array by comparing elements from each subarray and selecting the smaller one at each step.

Constraints

  • Requires additional O(n) space for the merging process
  • Slower than Quick Sort for small datasets due to recursion overhead
  • Excellent for linked lists as it doesn't require random access
  • Stable sort (maintains relative order of equal elements)

Step-by-step explanation

Arguments:

  • Array to be sorted - array
  • Left index of subarray - left
  • Right index of subarray - right
  • Temporary array for merging - tempArray
  • Left subarray (sorted) - leftArray
  • Right subarray (sorted) - rightArray

Explanation:

  • Divide the unsorted array into two halves at the middle index
  • Recursively sort the left half array[left..mid]
  • Recursively sort the right half array[mid+1..right]
  • Merge the two sorted halves back together:
    • Compare elements from both halves one by one
    • Always take the smaller element and place it in the merged array
    • Continue until all elements from both halves are merged
  • Repeat until the entire array is sorted

Returns:

Returns nothing (sorts array in-place in most implementations)
Some implementations may return a new sorted array while leaving the original unchanged
No explicit return value (void function in most in-place implementations)

Example

1
#include <vector>
2


3
void merge(std::vector<int>& arr, int left, int mid, int right) {
4
    int n1 = mid - left + 1;
5
    int n2 = right - mid;
6


7
    std::vector<int> L(n1), R(n2);
8
    for (int i = 0; i < n1; ++i) L[i] = arr[left + i];
9
    for (int j = 0; j < n2; ++j) R[j] = arr[mid + 1 + j];
10


11
    int i = 0, j = 0, k = left;
12
    while (i < n1 && j < n2) {
13
        if (L[i] <= R[j]) arr[k++] = L[i++];
14
        else arr[k++] = R[j++];
15
    }
16
    while (i < n1) arr[k++] = L[i++];
17
    while (j < n2) arr[k++] = R[j++];
18
}
19


20
void mergeSort(std::vector<int>& arr) {
21
    int n = (int)arr.size();
22
    for (int curr_size = 1; curr_size <= n - 1; curr_size *= 2) {
23
        for (int left_start = 0; left_start < n - 1; left_start += 2 * curr_size) {
24
            int mid = std::min(left_start + curr_size - 1, n - 1);
25
            int right_end = std::min(left_start + 2 * curr_size - 1, n - 1);
26
            merge(arr, left_start, mid, right_end);
27
        }
28
    }
29
}