Skip to main content

Merge Sort

Merge Sort is an efficient and stable sorting algorithm based on the divide-and-conquer paradigm, widely used in scenarios requiring stable sorting. It recursively divides an array into smaller subarrays, sorts them individually, and then merges them into a sorted array. This article explains the principle and steps of Merge Sort in detail, providing code examples in C and Go to help beginners get started quickly.

Principle​

The core idea of Merge Sort is:

  1. Divide: Recursively divide the array into two subarrays until the subarray length is 1 (a single element is considered sorted).
  2. Conquer: Merge two sorted subarrays to create a new sorted array.
  3. Repeat the above steps until the entire array is sorted.

Its time complexity is O(n log n), where n is the length of the array, and it remains consistent regardless of the input data. Merge Sort requires additional space to store temporary arrays, so its space complexity is O(n). Its stability makes it suitable for scenarios where the relative order of equal elements needs to be preserved.

Steps​

Assuming we want to sort an integer array in ascending order, here are the detailed steps for Merge Sort:

  1. Partition: Divide the array into two roughly equal subarrays and recursively sort each subarray.
  2. Termination Condition: When the subarray length is 1, stop partitioning (a single element is already sorted).
  3. Merge: Merge two sorted subarrays into a single sorted array by comparing the elements of the two subarrays and sequentially selecting the smaller element to place in the resulting array.
  4. Repeat: Recursively perform the above steps for all subarrays until the entire array is sorted.

Implementation​

Here is the C implementation of Merge Sort, with detailed comments to aid understanding.

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

// Merge two sorted subarrays
void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1; // Length of the left subarray
    int n2 = right - mid;    // Length of the right subarray
    
    // Create temporary arrays
    int *L = (int *)malloc(n1 * sizeof(int));
    int *R = (int *)malloc(n2 * sizeof(int));
    
    // Copy data to temporary arrays
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    
    // Merge the temporary arrays back into the original array
    i = 0;    // Index of the left subarray
    j = 0;    // Index of the right subarray
    k = left; // Index of the merged array
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    // Copy the remaining elements of the left subarray
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    
    // Copy the remaining elements of the right subarray
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
    
    // Free the temporary arrays
    free(L);
    free(R);
}

// Merge Sort function
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2; // Calculate the middle index
        
        // Recursively sort the left half
        mergeSort(arr, left, mid);
        // Recursively sort the right half
        mergeSort(arr, mid + 1, right);
        
        // Merge the sorted subarrays
        merge(arr, left, mid, right);
    }
}

// Helper function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Main function to test merge sort
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Original array: ");
    printArray(arr, n);
    
    mergeSort(arr, 0, n - 1);
    
    printf("Sorted array: ");
    printArray(arr, n);
    
    return 0;
}
Compile & Run
$ gcc -o bin/merge-sort main.c
$ bin/merge-sort 
Original array: 64 34 25 12 22 11 90 
Sorted array: 11 12 22 25 34 64 90 
$

Summary​

The core of Merge Sort is to recursively divide the array into smaller chunks using the divide-and-conquer approach, sort them individually, and then merge them into a sorted array, ensuring stable sorting characteristics.

Copyright Notice: Freely reproduced, non-commercial, no derivatives, attribution, and keep the source.

Author: afxcn

Source: https://gostartkit.com/docs/algo/merge-sort

Date Published: June 28, 2025