Merge Sort Explained: How It Achieves O(n log n)

One of the most efficient sorting algorithms is Merge Sort. Its fundamental working principle is based on the Divide and Conquer approach and recursion. The foundation of this algorithm was established in 1945 by John von Neumann, and it is still considered one of the most important sorting algorithms in computer science today.

Merge Sort consists of two main phases:

Divide: The list is recursively divided into two halves until each sublist contains only a single element.

Merge: The resulting sublists are then merged back together in sorted order, producing the final sorted list.

Let’s look at the Python implementation of the Merge Sort algorithm.

def merge_sort(nums):
    if len(nums) <= 1:
        return nums

    mid = len(nums) // 2

    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])

    return result

Unlike Quick Sort, one of the greatest advantages of Merge Sort is that its performance does not depend on the order of the input data. Whether the data is already sorted, randomly arranged, or sorted in reverse order, the algorithm performs the same number of divide and merge operations.

As a result, the time complexity of Merge Sort remains the same in the best, average, and worst cases:

O(n log n)

To understand why, let’s consider the following list:

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

Level 0:

8 elements

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

Level 1:

The 8 element list is divided into two halves:

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

Level 2:

The 4 element list is divided into two halves:

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

Level 3:

Each 2 element sublist is split into individual elements:

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

The division process stops here, as each sublist contains only one element. Since log_2(8) = 3, the divide phase consists of 3 levels. We can now move on to the merge phase.

Let’s start by merging the sublists at Level 3:

[38] + [27] =[27,38]

[43] + [3] =[3,43]

[9] + [82] =[9,82]

[10] + [1] =[1,10]

If we merge the sublists at Level 2:

[27,38] =[3,43]

[3,27,38,43]

[9,82] + [1,10]

[1,9,10,82]

Next, we merge the two sorted sublists at Level 1:

[3,27,38,43]
+
[1,9,10,82]
=

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

At each level, all 8 elements are processed exactly once. Since there are 3 levels in the recursion tree, the total amount of work performed is 8*3=24.In general, for a list of size n, the recursion tree has log₂(n) levels, and each level processes n elements. Therefore, the overall time complexity of Merge Sort is O(n log n).

One drawback of Merge Sort is that it is not an in-place sorting algorithm. During the merge phase, additional memory is required to store temporary arrays while combining the sorted sublists. As a result, the space complexity of Merge Sort is O(n).

Despite its extra memory requirements, Merge Sort remains an excellent choice for large datasets and systems where predictable performance is important, as it consistently achieves O(n log n) time complexity regardless of the input order.