Skip to content

An In-Depth Guide to Understanding Merge Sort

Hey there! Were you trying to wrap your head around sorting algorithms and got intrigued by merge sort? As a fellow computer science enthusiast, I‘m excited to take you on a deep yet friendly tour of what merge sort is, how it works, and why it‘s such an elegant sorting algorithm. Grab a snack, sit back, and get ready to become a merge sort expert!

Overview of Merge Sort

At its core, merge sort is an efficient sorting algorithm that works by breaking an array into smaller subarrays, sorting those subarrays, and finally merging them back together into the final sorted array. It‘s considered a "divide and conquer" algorithm because it attacks a big sorting problem by recursively dividing an array and conquering the small sorts.

But just how does this work? What is this mysterious "merge" step? By the time you‘re done reading, these questions will all be clear as day so let‘s plunge in!

The Origins of Merge Sort

Before implementing anything, it‘s good to know where merge sort comes from. After all, understanding the history often makes the purpose behind concepts obvious!

Merge sort was invented in 1945 by John von Neumann, who was a pioneer in the fields of mathematics, physics, computer science and more. At the time, John was exploring the technique of divide and conquer for designing algorithms where:

  1. You break a problem into smaller sets of the same problem.
  2. Solve the small problems in some way.
  3. Use these solutions to build the solution for the original problem.

For example, say you had 8 blocks to arrange from shortest to tallest. Using divide-and-conquer thinking, you could:

  1. Break the 8 blocks into 2 sets of 4 blocks each.
  2. Sort each small set of 4 from shortest to tallest.
  3. Merge the 2 small sorted towers into bigger sorted tower of all 8 blocks.

John applied this powerful technique to the pesky problem of sorting arrays efficiently, leading to his invention of merge sort in 1945. Since then, it has cemented its place as one of the most elegant sorting algorithms.

Now that you know the "why" behind merge sort, let‘s get into the details of precisely how it works!

How The Merge Sort Algorithm Works

When it comes to sorting an array of numbers, merge sort works in three key stages:

1. Divide the Array Recursively

In the first step, the array is divided in half recursively until atomic subarrays of just 1 element are obtained.

For example, let‘s consider an array with 8 elements, named "A":

A = [8, 5, 3, 2, 9, 4, 0, 1]

First, this entire array "A" is considered the input. It is split into two halves of size 4 elements each (dividing it "in half" based on number of elements):

Left subarray = [8, 5, 3, 2]   
Right subarray = [9, 4, 0 1]

Next, these subarrays are again divided recursively in the same way:

Animated diagram showing array getting divided recursively into subarrays

We continue this process of breaking down subarrays until we are left with atomic subarrays of just one element each:

[[8], [5], [3], [2], [9], [4], [0], [1]]

This stage exemplifies merge sort‘s divide & conquer approach. We‘ve taken a big, messy array and turned it into tiny singular arrays that are already inherently sorted!

2. Sort the Subarrays

Once we‘ve hit atomic subarrays, each subarray trivially has only one element and requires no actual "sorting".

But now, we can merge adjacent subarrays of size 1 into subarrays of size 2:

[[5, 8], [2, 3], [4, 9], [0, 1]]

And here is the "sorting" magic – as these subarrays of size 2 are merged, the elements are compared and sorted into ascending order.

In the first merged subarray [5, 8], the 5 is less than 8 so the elements remain unchanged. In [2, 3], the 2 and 3 end up sorted. The end result are sorted subarrays of size 2: 

[[3, 5], [0, 2], [4, 9], [1, 8]]

Similarly, these sorted arrays can be merged into sorted arrays of size 4:

[[0, 2, 3, 5], [1, 4, 8, 9]]

And so on until the full array is re-built. Pretty neat, right!?

3. Merge the Subarrays Back

As the recursive divide process continues on, we eventually reach tiny 1-element subarrays. From that point, we merge them back together to reform the original array in sorted order.

Let‘s see this in action for our array.

First, the size 1 subarrays are merge-sorted into size 2: 

[[2, 3], [4, 5], [0, 8], [1, 9]]

Next, they are merged into size 4:

[[0, 2, 3, 5], [1, 4, 8, 9]

Finally, the two halves combine:

[0, 1, 2, 3, 4, 5, 8, 9]

And voila! Like magic, we sorted the entire array in only 2 merge rounds. Pretty efficient given the original jumbled array, right?

This entire process is easier visualized as a sorted order tree:

merge sort array tree visualization

Let‘s see one more concrete example to drive home the concepts before diving into some code.

Walkthrough of an Array Getting Merge Sorted

For additional clarity, let‘s go through a step-by-step example of an array getting merge sorted.

Given this initial unsorted array:

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

Step 1: Divide Array Recursively

The array is divided into left and right subarrays:

Left = [38, 27] 
Right = [43, 3, 82, 9]

Again divide recursively:

Left = [[38], [27]]
Right = [[43], [3], [82], [9]]

We‘ve hit atomic subarrays, so now we merge and sort!

Step 2: Merge and Sort Subarrays

The size 1 arrays are merged into sorted size 2 arrays:

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

Merge again:

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

Last merge!

Step 3: Merge Everything

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

The full array is now sorted in ascending order via merge sort! Let‘s implement it in code next.

Python Implementation of Merge Sort

We‘ve covered quite a lot about merge sort already. Now let‘s implement the algorithm in Python to see it in action.

The key parts are:

  1. Recursive function to handle divide steps
  2. Merging function to merge and sort subarrays
  3. Driver code to test it out

Here is the full code:

def mergeSort(arr):
    if len(arr) > 1:

        # Finding the mid index
        mid = len(arr)//2

        # Dividing array  
        L = arr[:mid]   
        R = arr[mid:]


        # Recursively sorting the subarrays      
        mergeSort(L)    
        mergeSort(R)

        i = j = k = 0

        # Copy elements back to original array
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        # Checking if any element left
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

# Print the array          
def printList(arr):
    for i in range(len(arr)):     
        print(arr[i], end=" ")
    print()

# Driver code
if __name__ == ‘__main__‘:
    arr = [10, 3, 15, 7, 8, 23, 98, 29]  
    mergeSort(arr)
    print("Sorted array is: ")
    printList(arr)

When we run the Python implementation of merge sort, here is the output:

merge sort python output

And there you have it – the array sorted in ascending order via merge sort!

Now that you‘ve become a merge sort pro, let‘s analyze its performance and complexity next.

Time and Space Complexity Analysis

Like with any algorithm, it‘s important to understand merge sort‘s time and space complexities. This sheds light on when it performs best as well as its limitations.

Time Complexity

Merge sort has a time complexity of O(n log n) across best, average, and worst case scenarios. This equation breaks down as:

n – Number of elements in array
log n – Number of divide & merge rounds

For merge sort to sort an array of size n, approximately log(n) rounds of merging are required. And every round iterates through n elements to do comparison and merging. Putting it together gives us O(n log n) time complexity.

Let‘s analyze the iterative divide and merge rounds through a visual for a 16 element array:

merge sort time complexity visualization

In code terms, here is how the number of divide-merge rounds approximately doubles in each stage:

Array size - n = 16 

Round 1: Divide into n/2 = 16/2 = 8 subarrays  
Round 2: Divide into n/4 = 16/4 = 4 subarrays  
Round 3: Divide into n/8 = 16/8 = 2 subarrays
Round 4: Divide into n/16 = 16/16 = 1 subarray (size 1)

Total rounds ~ log2(n) = log2(16) = 4 rounds

This O(n log n) time classifies merge sort as an efficient sorting algorithm, especially for large amounts of data. This is a key reason why merge sort is popular!

Space Complexity

Merge sort has a space complexity of O(n). This is because additional memory is needed to temporarily store the divided subarrays as they get merged.

In the worst case scenario, space for ???n/2??? subarrays of size ???n/2??? is needed. This equates to a space complexity of:

    O(n/2 * n/2) = O(n^2/4) = O(n)

So in summary, merge sort requires equal space to the input data for temporaries. The space overhead is one drawback compared to in-place algorithms like quicksort that use O(log n) space.

Real-World Applications of Merge Sort

Now that you know how merge sort ticks, where is it actually used? Here are some of its handy, real-world applications:

1. External Sorting

When data grows too large to fit into memory, external sorting is used. Reads and writes to disk are the bottleneck here.

Merge sort sequentially accesses data making it perfect for external sorting where data sits on slower disks.

2. Sort Big Data & Databases

With Big Data and databases growing exponentially, fast & efficient sorting is crucial.

Merge sort‘s O(n log n) speed, stability, and external sorting abilities make it the go-to for sorting database tables and big data.

3. Count Inversions

The number of inversions in an array indicates how far it is from being sorted.

Merge sort can efficiently count inversions as it does merging. This has applications in areas like physics simulations.

There are many more applications, but these highlights demonstrate merge sort‘s versatile utility!

Optimizing Merge Sort for Faster Performance

Merge sort already has great time complexity. But we can tweak it to run even faster:

  • For small subarrays under 32 elements, rather than recursively dividing, use insertion sort which works faster on tiny arrays.

  • Store indices of elements rather than copying entire elements directly. This skips expensive copy operations.

  • Optimize the merge operation to leverage sequential access and disk caching during external sorting.

  • Use multi-threading – each recursive call can run parallely as a separate thread and combine results.

These optimizations can speed up merge sort by 2x to 3x for large datasets!

Concluding Thoughts on Merge Sort

And with that, you should have a rock-solid understanding of merge sort – from its origins all the way to optimizations! Here are the key takeaways:

  • Merge sort is an elegant divide-and-conquer algorithm invented by John Von Neumann in 1945.

  • It divides an array into smaller subarrays, recursively sorts them, and merges sorted pieces back together.

  • It has a time complexity of O(n log n) and space complexity of O(n).

  • Merge sort is useful for external sorting, big data, counting inversions and more thanks to its speed and stability.

  • Optimizations like using insertion sort for small data can further boost performance.

Whether you‘re prepping for an interview or just curiosity driven, I hope you‘ve thoroughly enjoyed this deep dive into understanding merge sort. Merge sort exemplifies how even complex concepts become intuitive when explained right. Thanks for sticking through right to the very end!

Tags: