Merge Sort - Algorithm, Visualization, Examples

Problem Statement❯

Given an array of integers, your task is to sort the array in ascending order using the Merge Sort algorithm.

Merge Sort is a divide and conquer algorithm. It divides the array into halves, recursively sorts them, and then merges the sorted halves into one final sorted array.

This algorithm is stable and guarantees a worst-case time complexity of O(n log n).

Examples❯

Input Array	Sorted Output	Description
[4, 2, 7, 1, 9, 3]	[1, 2, 3, 4, 7, 9]	Unsorted array is recursively divided and merged into a sorted version.
[1, 2, 3, 4]	[1, 2, 3, 4]	Already sorted input still goes through divide and merge steps.
[4, 4, 4, 4]	[4, 4, 4, 4]	All elements are equal. Merge Sort maintains the original order (stable).
[10]	[10]	Single-element array is already sorted. No merging needed.
[]	[]	Empty array returns an empty result. No action is performed.
[5, -2, 0, 3, -7]	[-7, -2, 0, 3, 5]	Handles negative numbers and zero correctly in sorting.

Visualization Player

Solution❯

Understanding the Problem

Imagine you have a messy list of numbers — like cards scattered on a table — and your goal is to sort them in increasing order. The problem we’re solving is: How can we sort an array efficiently?

One powerful way to do this is by using an algorithm called Merge Sort. It doesn't sort the whole thing in one go. Instead, it breaks the array into smaller parts, sorts those, and then puts them back together — all in the right order!

Our Strategy: Divide and Conquer

Merge Sort uses a classic strategy called Divide and Conquer. That means:

First, divide the array into halves.
Then, recursively sort each half.
Finally, merge the sorted halves into a single sorted array.

Step-by-Step Example

Let’s go through a clear example to see how Merge Sort works in action.

Input: [4, 2, 7, 1]

Step 1: Divide the array into two halves → [4, 2] and [7, 1]

Step 2: Break those down further → [4], [2], [7], [1]

Now we have individual elements, and by definition, each single-element array is already sorted.

Step 3: Merge them back in sorted order:

[4] and [2] → merge into [2, 4]
[7] and [1] → merge into [1, 7]

Step 4: Merge [2, 4] and [1, 7] → final result: [1, 2, 4, 7]

Exploring Different Edge Cases

Case 1: Already Sorted Array

[1, 2, 3, 4] is already sorted. Merge Sort will still divide and merge, but it won’t need to do much actual rearranging.

Case 2: All Elements Are the Same

Input: [5, 5, 5, 5] → Output: [5, 5, 5, 5]

Merge Sort keeps the original order, which is known as stability.

Case 3: Single Element

Input: [10] → Already sorted, nothing to do.

Case 4: Empty Array

Input: [] → No elements to sort, so the output is also [].

Case 5: Negative Numbers

Merge Sort handles all numbers just fine, even if they’re negative.

Example: [5, -2, 0] → [-2, 0, 5]

Why Merge Sort Is a Great Choice

Merge Sort always takes O(n log n) time — even in the worst case — which is very efficient for large datasets. Plus, because it's a stable sort, it's perfect when the relative order of equal elements matters (like sorting records by multiple criteria).

Algorithm Steps❯

Divide the unsorted array into n subarrays, each containing one element.
Repeatedly merge subarrays to produce new sorted subarrays until there is only one subarray remaining.
The final subarray is the sorted array.

Code

C++

Python

Java

Rust

Kotlin

Swift

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

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int *L = (int*) malloc(n1 * sizeof(int));
    int *R = (int*) malloc(n2 * sizeof(int));
    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
    int i = 0, j = 0, k = l;
    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 l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

int main() {
    int arr[] = {6, 3, 8, 2, 7, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    mergeSort(arr, 0, n - 1);
    printf("Sorted array is: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(n log n)	Merge Sort always divides the array into halves and merges them, regardless of the input order. Even if the array is already sorted, it still performs the same number of comparisons and merges.
Average Case	O(n log n)	In the average case, the array is recursively divided into halves (log n levels), and merging at each level takes O(n) time. Therefore, total time complexity is O(n log n).
Worst Case	O(n log n)	Even in the worst case, Merge Sort does not change its behavior — it still performs log n levels of merging with O(n) work at each level, leading to O(n log n) time.

Space Complexity❯

O(n)

Explanation: Merge Sort requires additional space to store temporary subarrays during the merge process. This auxiliary space grows linearly with the input size.

⬅ Previous TopicInsertion Sort

Next Topic ⮕Quick Sort

Comments

Loading comments...