Merge Sort Algorithm Explained

Merge Sort is a powerful divide-and-conquer sorting algorithm that sorts an array by dividing it into smaller parts, sorting those parts, and then merging them back together in sorted order.

Merge Sort is important because it has a guaranteed time complexity of O(n log n) in the best case, average case, and worst case. This makes it more predictable than algorithms such as Quicksort, which can degrade to O(n²) in the worst case if the pivot selection is poor.

Introduction

Sorting is one of the most important operations in computer science. Developers use sorting to organize numbers, names, dates, prices, scores, database results, files, products, and many other types of data.

Simple sorting algorithms such as Bubble Sort, Selection Sort, and Insertion Sort are useful for learning, but they are not efficient for large datasets because their average and worst-case time complexity is usually O(n²).

Merge Sort introduces a more efficient way of thinking. Instead of repeatedly comparing neighboring elements or searching for the smallest value, it divides the array into smaller arrays, sorts them recursively, and merges the sorted pieces back together.

What Is Merge Sort?

Merge Sort is a comparison-based sorting algorithm that follows the divide-and-conquer strategy. It divides the input array into two halves, recursively sorts each half, and then merges the two sorted halves into one sorted array.

The main idea is simple:

  • Divide the array into two halves.

  • Keep dividing each half until each subarray has one element.

  • A single-element array is already sorted.

  • Merge the small sorted arrays back together.

  • Continue merging until the whole array is sorted.

Merge Sort is called “merge” sort because the most important operation is merging two sorted arrays into one larger sorted array.

Divide and Conquer in Merge Sort

Merge Sort is a classic example of divide and conquer. This strategy solves a large problem by breaking it into smaller problems of the same type.

In Merge Sort, divide and conquer works like this:

  • Divide: Split the array into two halves.

  • Conquer: Recursively sort each half.

  • Combine: Merge the sorted halves into one sorted array.

This recursive structure is what allows Merge Sort to achieve O(n log n) performance.

Why Merge Sort Is Important

Merge Sort is important because it provides reliable performance. No matter how the input array is arranged, Merge Sort still divides the array in the same way and merges values systematically.

This makes Merge Sort useful for understanding:

  • Recursion.

  • Divide-and-conquer algorithms.

  • Stable sorting.

  • Guaranteed O(n log n) performance.

  • The difference between sorting in place and using extra memory.

Merge Sort is also a foundation for many advanced algorithmic ideas and is commonly discussed in data structures and algorithms courses.

How Merge Sort Works

Merge Sort works in two main phases: splitting and merging.

During the splitting phase, the algorithm keeps dividing the array into two halves until each subarray contains only one element. A single element is already sorted by definition.

During the merging phase, the algorithm combines two sorted subarrays into one sorted array. It compares the first elements of both subarrays and repeatedly takes the smaller value.

The algorithm continues this process until all subarrays are merged back into one fully sorted array.

Manual Run Example

Let us manually sort the following array using Merge Sort:

[8, 3, 5, 4, 7, 6, 1, 2]

The goal is to sort the array in ascending order.

Step 1: Split the Array

First, Merge Sort divides the array into two halves:

[8, 3, 5, 4]    [7, 6, 1, 2]

Then each half is divided again:

[8, 3]    [5, 4]    [7, 6]    [1, 2]

Then each pair is divided again until every subarray has one element:

[8] [3] [5] [4] [7] [6] [1] [2]

At this point, every subarray is sorted because each one contains only one element.

Step 2: Merge Single Elements

Now the algorithm starts merging single-element arrays into sorted pairs.

Merge [8] and [3]:

[8] + [3] = [3, 8]

Merge [5] and [4]:

[5] + [4] = [4, 5]

Merge [7] and [6]:

[7] + [6] = [6, 7]

Merge [1] and [2]:

[1] + [2] = [1, 2]

After the first merge level, we have:

[3, 8]    [4, 5]    [6, 7]    [1, 2]

Step 3: Merge Sorted Pairs

Now Merge Sort merges the sorted pairs.

Merge [3, 8] and [4, 5]:

Left:  [3, 8]
Right: [4, 5]

Compare the first values:

3 < 4, so take 3
8 > 4, so take 4
8 > 5, so take 5
Only 8 remains, so take 8

The merged result is:

[3, 4, 5, 8]

Now merge [6, 7] and [1, 2]:

Left:  [6, 7]
Right: [1, 2]

Compare the first values:

6 > 1, so take 1
6 > 2, so take 2
Only 6 and 7 remain, so take both

The merged result is:

[1, 2, 6, 7]

After this merge level, we have:

[3, 4, 5, 8]    [1, 2, 6, 7]

Step 4: Final Merge

Now we merge the two sorted halves:

Left:  [3, 4, 5, 8]
Right: [1, 2, 6, 7]

The merge process works step by step:

Compare 3 and 1 → take 1
Compare 3 and 2 → take 2
Compare 3 and 6 → take 3
Compare 4 and 6 → take 4
Compare 5 and 6 → take 5
Compare 8 and 6 → take 6
Compare 8 and 7 → take 7
Only 8 remains → take 8

The final sorted array is:

[1, 2, 3, 4, 5, 6, 7, 8]

Final Sorted Array

[1, 2, 3, 4, 5, 6, 7, 8]

This manual run shows the core idea of Merge Sort. The algorithm first breaks the array into very small parts, then builds the sorted result by merging those parts in the correct order.

Merge Sort Recursion Tree

Merge Sort can be visualized as a recursion tree. The array is repeatedly divided until each part contains one element.

[8, 3, 5, 4, 7, 6, 1, 2]
              /                  \
      [8, 3, 5, 4]          [7, 6, 1, 2]
        /       \             /       \
    [8, 3]    [5, 4]      [7, 6]    [1, 2]
     /  \      /  \        /  \      /  \
   [8] [3]  [5] [4]    [7] [6]  [1] [2]

Then the merge phase builds the sorted array from the bottom up:

[8] [3]  [5] [4]    [7] [6]  [1] [2]
   \ /      \ /        \ /      \ /
 [3,8]    [4,5]      [6,7]    [1,2]
      \     /             \     /
   [3,4,5,8]           [1,2,6,7]
             \         /
      [1,2,3,4,5,6,7,8]

This tree structure explains why Merge Sort has log n levels of recursion and why each level requires O(n) merging work.

The Merge Step Explained

The merge step is the heart of Merge Sort. It takes two sorted arrays and combines them into one sorted array.

For example:

Left:  [3, 8]
Right: [4, 5]

Both arrays are already sorted. The merge function compares the first available value in each array and chooses the smaller one.

The process is:

Compare 3 and 4 → take 3
Compare 8 and 4 → take 4
Compare 8 and 5 → take 5
Only 8 remains → take 8

The result is:

[3, 4, 5, 8]

This works because both input arrays are already sorted. The merge function does not need to compare every value with every other value.

Merge Sort Algorithm Steps

The Merge Sort algorithm can be described using these steps:

  1. If the array has zero or one element, return it because it is already sorted.

  2. Find the middle index of the array.

  3. Split the array into left and right halves.

  4. Recursively apply Merge Sort to the left half.

  5. Recursively apply Merge Sort to the right half.

  6. Merge the two sorted halves.

  7. Return the merged sorted array.

The base case is important. Without it, the recursive calls would never stop.

Pseudocode

mergeSort(array):
    if length(array) <= 1:
        return array

    middle = length(array) / 2

    left = mergeSort(first half of array)
    right = mergeSort(second half of array)

    return merge(left, right)

The merge function can be described like this:

merge(left, right):
    result = empty array

    while left is not empty and right is not empty:
        if first element of left <= first element of right:
            move first element of left into result
        else:
            move first element of right into result

    append remaining elements from left
    append remaining elements from right

    return result

This pseudocode shows the main logic without depending on a specific programming language.

Merge Sort Example in PHP

Here is a clean PHP implementation of Merge Sort:

<?php

function mergeSort(array $numbers): array
{
    $length = count($numbers);

    if ($length <= 1) {
        return $numbers;
    }

    $middle = intdiv($length, 2);

    $left = array_slice($numbers, 0, $middle);
    $right = array_slice($numbers, $middle);

    return merge(
        mergeSort($left),
        mergeSort($right)
    );
}

function merge(array $left, array $right): array
{
    $result = [];
    $i = 0;
    $j = 0;

    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] <= $right[$j]) {
            $result[] = $left[$i];
            $i++;
        } else {
            $result[] = $right[$j];
            $j++;
        }
    }

    while ($i < count($left)) {
        $result[] = $left[$i];
        $i++;
    }

    while ($j < count($right)) {
        $result[] = $right[$j];
        $j++;
    }

    return $result;
}

$numbers = [8, 3, 5, 4, 7, 6, 1, 2];

$sortedNumbers = mergeSort($numbers);

print_r($sortedNumbers);

The output will be:

Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
    [5] => 6
    [6] => 7
    [7] => 8
)

This implementation is easy to read. It uses array_slice to split the array and a separate merge function to combine sorted halves.

Merge Sort Example in JavaScript

Here is the same algorithm implemented in JavaScript:

function mergeSort(numbers) {
    if (numbers.length <= 1) {
        return numbers;
    }

    const middle = Math.floor(numbers.length / 2);
    const left = numbers.slice(0, middle);
    const right = numbers.slice(middle);

    return merge(
        mergeSort(left),
        mergeSort(right)
    );
}

function merge(left, right) {
    const result = [];
    let i = 0;
    let j = 0;

    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i]);
            i++;
        } else {
            result.push(right[j]);
            j++;
        }
    }

    while (i < left.length) {
        result.push(left[i]);
        i++;
    }

    while (j < right.length) {
        result.push(right[j]);
        j++;
    }

    return result;
}

const numbers = [8, 3, 5, 4, 7, 6, 1, 2];

console.log(mergeSort(numbers));

The output will be:

[1, 2, 3, 4, 5, 6, 7, 8]

The JavaScript version follows the same divide-and-conquer logic as the PHP version. The syntax changes, but the algorithmic idea remains the same.

Merge Sort with Strings

Merge Sort can also be used to sort strings alphabetically. The same merge logic works as long as the values can be compared.

Input:
['Lina', 'Ali', 'Omar', 'Sara']

Sorted:
['Ali', 'Lina', 'Omar', 'Sara']

When sorting strings, developers should be careful with case sensitivity and locale rules. For real applications, built-in sorting functions may handle these details better.

Merge Sort with Objects

In real software projects, developers often sort arrays of objects or records by a specific field such as price, date, score, or name.

For example, products can be sorted by price:

<?php

function mergeProductsByPrice(array $left, array $right): array
{
    $result = [];
    $i = 0;
    $j = 0;

    while ($i < count($left) && $j < count($right)) {
        if ($left[$i]['price'] <= $right[$j]['price']) {
            $result[] = $left[$i];
            $i++;
        } else {
            $result[] = $right[$j];
            $j++;
        }
    }

    return array_merge(
        $result,
        array_slice($left, $i),
        array_slice($right, $j)
    );
}

This example shows that Merge Sort can be adapted to sort complex data structures by a custom field.

Time Complexity of Merge Sort

Time complexity describes how the running time of an algorithm grows as the input size increases. Merge Sort has very predictable time complexity because it always divides the array into halves and merges the results.

Merge Sort has the following time complexity:

  • Best case: O(n log n)

  • Average case: O(n log n)

  • Worst case: O(n log n)

This consistency is one of the main advantages of Merge Sort.

Why Merge Sort Is O(n log n)

Merge Sort gets O(n log n) from two parts of the algorithm: dividing and merging.

The array is divided in half repeatedly. The number of division levels is approximately log n.

n
n / 2
n / 4
n / 8
...
1

At each level, all elements are merged once. The total merging work at each level is O(n).

So the total work becomes:

O(n) work per level × O(log n) levels = O(n log n)

This is why Merge Sort is much more efficient than O(n²) algorithms for large datasets.

Best Case Time Complexity: O(n log n)

The best case happens when the array is already sorted.

[1, 2, 3, 4, 5, 6]

Even though the array is already sorted, Merge Sort still divides it into smaller parts and merges those parts back together. It does not simply stop after detecting that the input is sorted.

Therefore, the best case time complexity is:

O(n log n)

Average Case Time Complexity: O(n log n)

The average case happens when the array is in random order.

[8, 3, 5, 4, 7, 6, 1, 2]

Merge Sort still performs the same division structure and the same merge levels. The exact order of input values does not significantly change the number of levels or the amount of merging.

Therefore, the average case time complexity is:

O(n log n)

Worst Case Time Complexity: O(n log n)

The worst case also has O(n log n) time complexity.

This is different from Quicksort, where poor pivot choices can cause O(n²) behavior. Merge Sort does not depend on pivots. It always splits the array into halves and merges sorted parts.

Therefore, the worst case time complexity is:

O(n log n)

This guaranteed performance makes Merge Sort a reliable algorithm.

Space Complexity of Merge Sort

Merge Sort usually requires extra memory because it creates temporary arrays during the merge process.

The common space complexity of Merge Sort is:

O(n)

This extra memory is used to store the merged results. Recursive calls also use stack memory, but the main additional memory cost comes from temporary arrays.

Because of this, Merge Sort is usually not considered an in-place sorting algorithm in its standard implementation.

Is Merge Sort Stable?

Merge Sort is stable when implemented correctly.

A stable sorting algorithm preserves the relative order of equal elements. For example, if two products have the same price, a stable sort keeps them in the same order they appeared in the original list.

In Merge Sort, stability is preserved during the merge step if the algorithm chooses the left element first when two values are equal:

if left[i] <= right[j]:
    take left[i]

Using <= instead of only < helps keep equal elements in their original relative order.

Is Merge Sort In-Place?

Standard Merge Sort is not in-place because it uses extra arrays during merging.

An in-place algorithm sorts data without requiring significant additional memory. Merge Sort usually needs O(n) extra space, so it is not considered in-place in its common form.

There are advanced in-place merge techniques, but they are more complex and not usually used in beginner implementations.

Merge Sort vs Quicksort

Merge Sort and Quicksort are both divide-and-conquer sorting algorithms, but they behave differently.

Main differences include:

  • Merge Sort divides the array into halves first, then merges sorted parts.

  • Quicksort selects a pivot and partitions values around it.

  • Merge Sort has guaranteed O(n log n) time complexity.

  • Quicksort has average O(n log n), but worst case O(n²).

  • Merge Sort is stable when implemented correctly.

  • Quicksort is usually not stable.

  • Merge Sort usually needs O(n) extra memory.

  • Quicksort can often be implemented with less extra memory.

Quicksort is often faster in practice for arrays because of good cache performance and lower memory overhead. Merge Sort is preferred when stability and guaranteed performance are more important.

Merge Sort vs Insertion Sort

Insertion Sort is simple and efficient for small or nearly sorted arrays. Merge Sort is better for larger datasets because its time complexity is O(n log n).

Main differences include:

  • Insertion Sort has best case O(n), but average and worst case O(n²).

  • Merge Sort has O(n log n) in all cases.

  • Insertion Sort uses O(1) extra memory.

  • Merge Sort usually uses O(n) extra memory.

  • Both can be stable when implemented correctly.

Some real-world sorting systems use hybrid approaches, applying Merge Sort or another efficient algorithm for large data and switching to Insertion Sort for very small subarrays.

Merge Sort vs Bubble Sort and Selection Sort

Bubble Sort and Selection Sort are simple algorithms, but they are inefficient for large datasets. Their average and worst-case time complexity is O(n²).

Merge Sort is much more efficient for large inputs because it uses divide and conquer.

Bubble Sort:    O(n²)
Selection Sort: O(n²)
Merge Sort:     O(n log n)

For educational purposes, Bubble Sort and Selection Sort are useful because they are easy to understand. For performance, Merge Sort is much stronger.

When Should Developers Use Merge Sort?

Developers should consider Merge Sort when they need predictable performance and stable sorting.

Merge Sort is useful when:

  • The dataset is large.

  • Guaranteed O(n log n) performance is required.

  • Stable sorting is important.

  • The data is stored in a linked list.

  • Worst-case performance matters.

  • Extra memory usage is acceptable.

Merge Sort is especially suitable when consistent performance is more important than minimizing memory usage.

When Not to Use Merge Sort

Merge Sort may not be the best choice when memory is limited. Because it usually requires O(n) extra space, it can be less suitable for environments where memory usage must be very low.

Developers may avoid Merge Sort when:

  • The dataset is very small.

  • Memory usage must be minimal.

  • An in-place sort is required.

  • The programming language already provides a highly optimized built-in sorting function.

In most production applications, developers should use built-in sorting functions unless they have a specific reason to implement sorting manually.

Practical Example: Sorting Product Prices

Imagine an e-commerce system that needs to sort product prices from lowest to highest. Merge Sort can sort the list reliably.

<?php

$prices = [99.99, 29.99, 49.99, 19.99, 79.99];

$sortedPrices = mergeSort($prices);

print_r($sortedPrices);

The result will be:

Array
(
    [0] => 19.99
    [1] => 29.99
    [2] => 49.99
    [3] => 79.99
    [4] => 99.99
)

This example is simple, but it connects Merge Sort to real application data.

Practical Example: Sorting Posts by Date

Merge Sort can also be used to sort records by date if the comparison logic checks the date field.

For example, blog posts could be sorted from oldest to newest or newest to oldest. Because Merge Sort can be stable, posts with the same date can keep their original relative order.

This stability can be useful when sorting records that have duplicate keys.

Common Mistakes When Implementing Merge Sort

Beginners often understand the main idea of Merge Sort but make mistakes in the recursive implementation or the merge function.

Common mistakes include:

  • Forgetting the base case.

  • Calculating the middle index incorrectly.

  • Not returning the merged result.

  • Losing remaining elements after one side is exhausted.

  • Using < instead of <= and losing stability.

  • Confusing the splitting phase with the merging phase.

  • Creating too many unnecessary copies without understanding memory cost.

The most important detail is the merge step. If the merge function is wrong, the whole algorithm will return incorrect results.

Practical Checklist for Understanding Merge Sort

Before moving to more advanced algorithms, developers should be able to answer these questions:

  • What does divide and conquer mean?

  • Why does Merge Sort split the array into halves?

  • What is the base case of Merge Sort?

  • How does the merge function combine two sorted arrays?

  • Why is Merge Sort O(n log n)?

  • Why does Merge Sort need O(n) extra space?

  • Is Merge Sort stable?

  • How is Merge Sort different from Quicksort?

If these questions are clear, the developer understands the real logic behind Merge Sort instead of only memorizing the code.

Advantages of Merge Sort

Merge Sort has several important advantages.

  • It has guaranteed O(n log n) time complexity.

  • It is stable when implemented correctly.

  • It works well for large datasets.

  • It is predictable in best, average, and worst cases.

  • It is a strong example of divide and conquer.

  • It works well with linked lists.

These advantages make Merge Sort one of the most important sorting algorithms to learn.

Disadvantages of Merge Sort

Merge Sort also has limitations.

  • It usually requires O(n) extra memory.

  • It is not usually in-place.

  • It may be slower than Quicksort in practice for arrays because of extra memory operations.

  • It has more overhead than simple algorithms for very small arrays.

  • The recursive implementation may be harder for beginners at first.

Because of these limitations, Merge Sort is not always the best practical choice, even though it has excellent theoretical performance.

Merge Sort in Real Software Projects

Merge Sort concepts appear in many real software systems, especially when stable sorting and predictable performance are important.

Some programming languages and libraries use algorithms inspired by Merge Sort or combine Merge Sort ideas with other techniques. For example, stable sorting systems often use merge-based logic because merging sorted runs is reliable and predictable.

In backend applications, developers usually do not manually implement Merge Sort for normal business logic. Instead, they use built-in sorting functions or database ordering. However, understanding Merge Sort helps developers reason about performance, memory usage, stability, and algorithm design.

Conclusion

Merge Sort is a divide-and-conquer sorting algorithm that splits an array into smaller parts, sorts those parts recursively, and merges them back into one sorted array.

Its greatest strength is reliability. Merge Sort has O(n log n) time complexity in the best case, average case, and worst case. This makes it more predictable than algorithms that can become slow depending on the input arrangement.

Merge Sort is also stable when implemented correctly, which makes it useful when the relative order of equal elements matters. However, it usually requires O(n) extra memory, so it is not typically considered an in-place sorting algorithm.

For developers learning data structures and algorithms, Merge Sort is an essential algorithm. It teaches recursion, divide and conquer, merging, stability, time complexity, and the trade-off between speed and memory. Understanding Merge Sort prepares developers to study more advanced algorithms and to make better decisions when choosing sorting strategies in real software projects.