Merge Sort

Merge Sort Algorithm

Like Quick Sort, Merge Sort is extremely fast and is widely used in real-world programming. In fact, many programming languages (like Java) use a variation of Merge Sort for their built-in sorting functions!

Let's explore how it divides data to conquer massive sorting problems.

1. The Divide and Conquer Approach

Merge Sort literally cuts the problem in half over and over again.

The algorithm follows two main steps:

1. Divide: Keep cutting the array in half until you are left with arrays that only have 1 element each. (An array with 1 element is already perfectly sorted!)
2. Conquer (Merge): Pair up these 1-element arrays and merge them into a 2-element sorted array. Pair up the 2-element arrays into 4-element sorted arrays. Repeat until the whole array is rebuilt!

Merge Sort: Splitting down to single elements, then merging them back in perfect order.

2. A Step-by-Step Example

Let's trace how Merge Sort handles this array: [38, 27, 43, 3]

Phase 1: Divide (Splitting)

• Split in half: [38, 27] and [43, 3].
• Split those in half: [38], [27], [43], [3].
• We cannot split anymore. We now have four sorted arrays of length 1!

Phase 2: Conquer (Merging)

• Merge [38] and [27]. Which is smaller? 27. So they become [27, 38].
• Merge [43] and [3]. Which is smaller? 3. So they become [3, 43].
• Now we have two sorted arrays: [27, 38] and [3, 43].
• Merge them together! Compare the first items: 27 and 3. The 3 wins.
• Compare 27 and 43. The 27 wins.
• Compare 38 and 43. The 38 wins.
• Final sorted array: [3, 27, 38, 43].

3. Merge Sort Code Example

Below is the Python implementation of Merge Sort. It uses Recursion (a function calling itself) to continuously split the array, and a helper loop to merge the arrays back together.

def merge_sort(arr):
    if len(arr) > 1:
        # Find the middle point
        mid = len(arr) // 2
        # Divide the array elements
        left_half = arr[:mid]
        right_half = arr[mid:]
        # Recursively sort both halves
        merge_sort(left_half)
        merge_sort(right_half)
        # Conquer: Merge the sorted halves
        i = j = k = 0
        # Compare elements from left and right halves
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1
        # Check if any elements were left over
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1
        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
    return arr

numbers = [38, 27, 43, 3, 9, 82, 10]
print("Original:", numbers)
print("Sorted:", merge_sort(numbers))

4. Time and Space Complexity

• Time Complexity: O(n log n). This is Merge Sort's biggest strength! Because it divides the array exactly in half every time (which takes log n steps), and then merges them linearly (n steps), it is guaranteed to be extremely fast, even in the worst-case scenario!
• Space Complexity: O(n). This is its main weakness. Merge Sort requires extra memory space to hold the split left_half and right_half arrays while it is sorting.