Merge Sort in C

Analogy categoryAnalogies

1. Introduction

Merge sort is a classic divide-and-conquer sorting algorithm that guarantees O(n log n) time complexity in every case: best, average, and worst. It works by recursively splitting the array into two halves until each sub-array contains a single element (trivially sorted), and then merging those sub-arrays back together in sorted order. Because its performance does not degrade on already-sorted or reverse-sorted input, merge sort is widely used for sorting linked lists, external/disk-based sorting, and any scenario where predictable, consistent performance is more important than minimizing memory usage.

🏏

Cricket analogy: Merge sort is like organizing a huge squad of net bowlers into pairs, ranking each pair, then combining ranked pairs into a final bowling order — a method that takes the same predictable time whether the squad started scrambled or already in order, like the IPL auction pool.

2. Syntax

void mergeSort(int arr[], int left, int right);
void merge(int arr[], int left, int mid, int right);

/* Parameters:
   arr   - array of integers to sort in place
   left  - starting index of the current sub-array
   right - ending index of the current sub-array
   mid   - midpoint that splits [left, right] into two halves

   Initial call: mergeSort(arr, 0, n - 1); */

3. Explanation

mergeSort(arr, left, right) first checks if left < right; if the sub-array has more than one element, it computes mid = left + (right - left) / 2, then recursively sorts the left half [left, mid] and the right half [mid + 1, right]. Once both halves are individually sorted, the merge() function combines them: it copies the two halves into temporary arrays, then repeatedly compares the smallest remaining elements of each temporary array and writes the smaller one back into arr, advancing whichever pointer was used. Any leftover elements from either temporary array (once the other is exhausted) are copied directly, since they are already in sorted order.

🏏

Cricket analogy: mergeSort splits a squad list at mid, sorts each half recursively, like grouping batters then bowlers separately; merge() then compares the top prospect from each temp group and picks the stronger one repeatedly, dumping any leftovers straight in since they're already ranked.

Worked trace on [38, 27, 43, 3]: split into [38, 27] and [43, 3]. [38, 27] splits into [38] and [27], which merge to [27, 38]. [43, 3] splits into [43] and [3], which merge to [3, 43]. Finally, merge [27, 38] with [3, 43]: compare 27 vs 3 -> take 3; compare 27 vs 43 -> take 27; compare 38 vs 43 -> take 38; 43 is the only element left -> take 43. Result: [3, 27, 38, 43].

🏏

Cricket analogy: Tracing [38,27,43,3] is like sorting four batters' scores: split into [38,27] and [43,3]; merge each pair to [27,38] and [3,43]; then merge those, comparing 27 vs 3, 27 vs 43, 38 vs 43, landing on the final ranked list [3,27,38,43].

4. Example

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

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;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];

    free(L);
    free(R);
}

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);
    }
}

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

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

    mergeSort(arr, 0, n - 1);
    printArray(arr, n);
    return 0;
}

5. Output

text

3 27 38 43

6. Key Takeaways

Time complexity is O(n log n) in the best, average, and worst case, since the array is always split evenly and merged in linear time.
Space complexity is O(n) extra space because of the temporary L and R arrays used during merging.
Merge sort is a stable sort (the '<=' comparison in merge preserves the order of equal elements).
It is not an in-place algorithm in its classic form, unlike quick sort, due to the auxiliary arrays.
It is well suited for sorting linked lists and large external datasets that don't fit in memory.

Practice what you learned

1. What is the time complexity of merge sort in the worst case?

2. What is the auxiliary space complexity of the standard merge sort implementation shown?

3. In the merge step, why is the comparison 'L[i] <= R[j]' used instead of 'L[i] < R[j]'?

4. What is the value of mid when mergeSort is called with left = 0 and right = 3?

5. Which of these is true about merge sort compared to quick sort?

Was this page helpful?

Bubble Sort in C

Quick Sort in C

Related Study Notes in Programming

Browse all study notes

Programming

Apache Spark Study Notes

Programming · 30 topics

Programming

Apache Flink Study Notes

Programming · 30 topics

Programming

Hadoop Study Notes

Programming · 30 topics

Programming

Snowflake Study Notes

Programming · 30 topics

Programming

Apache Airflow Study Notes

Programming · 30 topics

Programming

dbt (Data Build Tool) Study Notes

Programming · 30 topics

Topics covered

#CProgrammingStudyNotes#Programming#MergeSortInC#Merge#Sort#Syntax#Explanation#Algorithms#Git#StudyNotes#SkillVeris

1. Introduction

2. Syntax

3. Explanation

4. Example

5. Output

6. Key Takeaways

Practice what you learned

You May Also Like

Related Reading

Related Study Notes in Programming

Topics covered