Master Merge Sort: Step‑by‑Step Explanation, Code, and Analysis

Algorithm Idea

Merge Sort is a stable, divide‑and‑conquer sorting algorithm. It recursively splits an array into halves until sub‑arrays of size 1 are reached, then merges the sorted sub‑arrays.

Steps

Divide the array of n elements into two halves.

Recursively split each half until each sub‑array contains a single element.

Merge the sorted sub‑arrays from the bottom up, repeatedly combining two sorted sequences.

Illustrative Example

Given arr = [3, 7, 8, 10, 2, 4, 6, 9], the first split yields [3, 7, 8, 10] and [2, 4, 6, 9]. Merging these produces [2, 3, 4, 6, 7, 8, 9, 10].

During merging, pointers i and j track the current elements of the left and right sub‑arrays, while k points to the position in the result array. The smaller element is copied to arr[k] and the corresponding pointer is advanced.

Algorithm Implementation (C)

#include <stdio.h>

void merge(int arr[], int L, int M, int R) {
    int LEFT_SIZE = M - L;
    int RIGHT_SIZE = R - M + 1;
    int left[LEFT_SIZE];
    int right[RIGHT_SIZE];
    int i, j, k;
    for (i = L; i < M; i++) left[i - L] = arr[i];
    for (i = M; i <= R; i++) right[i - M] = arr[i];
    i = 0; j = 0; k = L;
    while (i < LEFT_SIZE && j < RIGHT_SIZE) {
        if (left[i] < right[j]) arr[k++] = left[i++];
        else arr[k++] = right[j++];
    }
    while (i < LEFT_SIZE) arr[k++] = left[i++];
    while (j < RIGHT_SIZE) arr[k++] = right[j++];
}

void mergeSort(int arr[], int L, int R) {
    if (L >= R) return;
    int M = (L + R) / 2;
    mergeSort(arr, L, M);
    mergeSort(arr, M + 1, R);
    merge(arr, L, M + 1, R);
}

int main() {
    int arr[] = {8,7,2,10,3,9,4,6};
    int L = 0;
    int R = 7;
    mergeSort(arr, L, R);
    for (int i = 0; i <= R; i++) {
        printf("%d
", arr[i]);
    }
    return 0;
}

Algorithm Analysis

Time Complexity: O(n log n)

Space Complexity: O(n) – an auxiliary array of the same size as the input is required.

Stability: Merge Sort is stable because equal elements retain their original relative order.

Applicable Scenarios

Merge Sort is suitable when extra memory is available and stability is required, such as sorting linked lists or large data sets where predictable performance is important.