Offensive Security Researcher & Quantum Cryptography Analyst

Merge Sort Algorithm: Working, Explanation, and Divide-and-Conquer Sorting

Abdul Wahab Junaid
merge sort algorithm and working of this algorithm

merge sort algorithm and working of this algorithm

I think of merge sort as the most dependable sorting algorithm in my toolkit. It is a comparison-based, divide-and-conquer algorithm that guarantees O(n log n) performance every single time, regardless of how the input data is arranged. Unlike quick sort, merge sort never degrades to O(n²), which makes it my go-to choice whenever predictability matters more than raw average-case speed. It is also naturally stable, which is a property I lean on heavily whenever I need to preserve the relative order of equal elements, such as sorting records by a secondary key after already sorting by a primary one.

History and Background

Merge sort was invented by John von Neumann in 1945, making it one of the earliest algorithms designed specifically for electronic computers. Von Neumann described it in a report about the design of the EDVAC, one of the first stored-program computers, as a way to sort data efficiently using the “merge” operation as its foundation. The algorithm’s divide-and-conquer structure influenced decades of later algorithm design, and merge sort remains a canonical teaching example for that paradigm. Its guaranteed O(n log n) worst-case bound made it foundational to the theoretical study of sorting lower bounds in comparison-based models.

Problem Statement

I need a sorting algorithm that offers a guaranteed worst-case time complexity, is stable, and works well on data structures where random access is expensive or impossible, such as linked lists. Merge sort solves this by dividing the input into smaller pieces, sorting each piece independently, and then combining (“merging”) the sorted pieces back together — trading some extra memory for consistent, predictable performance.

Core Concepts

How It Works

I break merge sort into two clear phases:

  1. Divide: I repeatedly split the array into two halves until each piece contains a single element (or is empty), which is trivially sorted.
  2. Merge: I combine adjacent sorted pieces back together in sorted order, working my way back up the recursion tree until the entire array is merged into one fully sorted sequence.

Working Principle

The mechanism I rely on is that merging two already-sorted sequences is much simpler than sorting an unsorted one directly. I maintain two pointers, one for each subarray, and at each step I compare the elements the pointers reference, copying the smaller one into the output and advancing that pointer. Because both subarrays are already internally sorted before I merge them, I only need a single linear pass through both to produce a fully sorted combined sequence. This bottom-up recombination, repeated at every level of the recursion tree, is what builds the final sorted array from the ground up.

Mathematical Foundation

Merge sort’s recurrence relation reflects its divide-and-conquer structure precisely: I divide the array into two halves of size n/2 each, and merging them takes linear time relative to their combined size:

$$T(n) = 2T\left(\frac{n}{2}\right) + O(n)$$

Applying the Master Theorem with $a = 2$, $b = 2$, and $f(n) = O(n)$, since $f(n) = \Theta(n^{\log_b a}) = \Theta(n)$, this falls into Case 2, giving:

$$T(n) = O(n \log n)$$

This bound holds for the best, average, and worst cases alike, since the algorithm’s structure never depends on the arrangement of the input data — only on its size. The number of merge levels is:

$$\log_2 n$$

and each level performs O(n) total comparisons and copies, giving the overall $O(n \log n)$ bound.

Diagrams

flowchart TD
    A["[38,27,43,3,9,82,10]"] --> B["[38,27,43,3]"]
    A --> C["[9,82,10]"]
    B --> D["[38,27]"]
    B --> E["[43,3]"]
    C --> F["[9,82]"]
    C --> G["[10]"]
    D --> H["[38] [27]"]
    E --> I["[43] [3]"]
    F --> J["[9] [82]"]
    H --> K["merge -> [27,38]"]
    I --> L["merge -> [3,43]"]
    J --> M["merge -> [9,82]"]
    K --> N["merge -> [3,27,38,43]"]
    L --> N
    M --> O["merge -> [9,10,82]"]
    G --> O
    N --> P["merge -> [3,9,10,27,38,43,82]"]
    O --> P
sequenceDiagram
    participant Left as Left Subarray
    participant Right as Right Subarray
    participant Out as Output Array
    Left->>Out: Compare front elements
    Right->>Out: Compare front elements
    Note over Out: Copy smaller element, advance that pointer
    Out-->>Out: Repeat until one side is exhausted
    Out-->>Out: Copy remaining elements from the other side

Pseudocode

MERGE-SORT(A, left, right)
    if left < right
        mid = (left + right) / 2
        MERGE-SORT(A, left, mid)
        MERGE-SORT(A, mid + 1, right)
        MERGE(A, left, mid, right)

MERGE(A, left, mid, right)
    create temp arrays L[0..mid-left] and R[0..right-mid-1]
    copy A[left..mid] into L
    copy A[mid+1..right] into R

    i = 0, j = 0, k = left
    while i < length(L) and j < length(R)
        if L[i] <= R[j]
            A[k] = L[i]; i = i + 1
        else
            A[k] = R[j]; j = j + 1
        k = k + 1

    copy remaining elements of L into A
    copy remaining elements of R into A

Step-by-Step Example

I will sort [38, 27, 43, 3, 9, 82, 10].

Divide phase: I split repeatedly: [38,27,43,3] and [9,82,10] → [38,27], [43,3], [9,82], [10] → [38], [27], [43], [3], [9], [82], [10]

Merge phase (bottom-up):

Final sorted output: [3, 9, 10, 27, 38, 43, 82]

Time Complexity

Space Complexity

Merge sort requires O(n) additional space for the temporary arrays used during merging. This is its main trade-off compared to in-place algorithms like quick sort or heap sort — I am spending linear extra memory in exchange for guaranteed O(n log n) time and stability. In linked-list implementations, this overhead can be reduced significantly since merging can be done by re-linking nodes rather than copying values, bringing auxiliary space down to O(log n) for the recursion stack alone.

Correctness Analysis

I can prove merge sort’s correctness through structural induction on the size of the subarray being sorted. The base case, a subarray of size 0 or 1, is trivially sorted. For the inductive step, I assume both halves of size less than n are sorted correctly by the recursive calls, by the inductive hypothesis. The merge step then combines these two sorted sequences using a single linear scan that always selects the smaller of the two front elements, which guarantees the combined output is sorted — this is a direct consequence of the fact that once an element is placed, no element smaller than it can appear later in either remaining sequence. Since this holds at every level of recursion up to the full array, the entire array ends up correctly sorted.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>
#include <stdlib.h>

// Merge two sorted subarrays A[left..mid] and A[mid+1..right]
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int *L = (int *)malloc(n1 * sizeof(int));
    int *R = (int *)malloc(n2 * sizeof(int));

    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;

    // Merge the two temp arrays back into arr[left..right]
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy any remaining elements of L
    while (i < n1) {
        arr[k] = L[i];
        i++; k++;
    }

    // Copy any remaining elements of R
    while (j < n2) {
        arr[k] = R[j];
        j++; k++;
    }

    free(L);
    free(R);
}

// Recursive merge sort
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, n - 1);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Sample Input and Output

Input: [38, 27, 43, 3, 9, 82, 10]

Output: Sorted array: 3 9 10 27 38 43 82

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version