Merge Sort Algorithm

What is Merge Sort?

Merge Sort is a classic and highly efficient divide-and-conquer sorting algorithm. It works by recursively dividing the array into halves, sorting each half, and then merging the sorted halves back together. The final result is a fully sorted array.

Merge Sort is especially powerful because of its predictable performance and stability. It is used in many real-world applications where performance and order preservation are important.

How Merge Sort Works

1. Divide the array into two halves.
2. Recursively sort each half.
3. Merge the two sorted halves into one sorted array.

This divide–sort–merge approach continues until the array is broken down into individual elements (which are naturally sorted), and then built back up in a sorted order.

Time and Space Complexity

• Space Complexity: O(n) → uses temporary arrays
• Stable: ✅ Yes

When to Use Merge Sort

• When you need stable sorting
• When working with linked lists (easy to implement)
• When sorting large datasets with predictable performance
• When dealing with external sorting (e.g., sorting files too big for RAM)

Merge Sort – C++ Code Example

#include <iostream>
using namespace std;

// Merges two subarrays of arr[]
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Create temp arrays
    int* L = new int[n1];
    int* R = new int[n2];

    // Copy data
    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];

    // Merge the temp arrays back
    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++];
    }

    // Copy remaining elements
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];

    delete[] L;
    delete[] R;
}

// Recursively divides and sorts array
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);      // Sort left half
        mergeSort(arr, mid + 1, right); // Sort right half

        merge(arr, left, mid, right);   // Merge halves
    }
}

// Utility to print the array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    cout << endl;
}

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

    cout << "Original array:\n";
    printArray(arr, n);

    mergeSort(arr, 0, n - 1);

    cout << "Sorted array:\n";
    printArray(arr, n);

    return 0;
}

Output

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

Merge Sort – Visual Explanation (Step-by-Step)

We will sort:

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

Step 1: Divide the Array

Split recursively:

[38, 27, 43, 3, 9, 82, 10]
→ [38, 27, 43] and [3, 9, 82, 10]
→ [38], [27, 43] and [3, 9], [82, 10]
→ ...

Step 2: Sort and Merge

Start merging sorted chunks:

1. [27, 43] → sorted merge
2. [38], [27, 43] → merge → [27, 38, 43]
3. [3, 9] → sorted merge
4. [82, 10] → merge → [10, 82]
5. [3, 9], [10, 82] → merge → [3, 9, 10, 82]
6. Final merge: [27, 38, 43], [3, 9, 10, 82] →
   → [3, 9, 10, 27, 38, 43, 82]

Final Sorted Array

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

Summary

• Merge Sort is a powerful, recursive, divide-and-conquer algorithm.
• Always guarantees O(n log n) performance.
• Stable and reliable, though it uses extra space.
• Best suited for large datasets or when stability is required.