Merge Sort Algorithm in Python | Explained

Merge Sort is a classic divide-and-conquer sorting technique. It divides the list into two halves, sorts each half recursively, and then merges the two sorted halves.

So let’s get started with the [Problem Link].

The major steps are:

1. Divide: Split the array into two parts.
2. Conquer: Recursively sort each half.
3. Combine: Merge the two sorted halves into a single sorted list.

This approach ensures a guaranteed time complexity of O(nlog⁡n) in the worst, average, and best cases, making Merge Sort a reliable and efficient sorting algorithm, especially for large datasets.

1. The merge_sort Function

def mergeSort(self, arr, l, r):
    if l < r:
        mid = (l + r) // 2
        # Sort first and second halves
        self.mergeSort(arr, l, mid)
        self.mergeSort(arr, mid + 1, r)
        self.merge(arr, l, mid, r)

Explanation

1. Base Condition: If the list has 0 or 1 elements, it’s already sorted, so return it as is.
2. Find Midpoint: Compute mid = len(arr) // 2 to split the array into two nearly equal halves.
3. Recursive Sort:
   • Recursively call merge_sort(left_half) and merge_sort(right_half).
   • This breaks each subarray further until it reaches the base condition (lists of size 1 or 0).
4. Merge: After both halves return in sorted form, pass them to merge_array to produce a single, sorted list.

2. The merge_array Function

def merge(self, arr, l, mid, r):
    # Create temp arrays
    left = arr[l : mid + 1]
    right = arr[mid + 1 : r + 1]

    i = 0
    j = 0
    k = l

    # Merge the temp arrays back into arr[l..r]
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
        k += 1

    # Copy the remaining elements of left[], if any
    while i < len(left):
        arr[k] = left[i]
        i += 1
        k += 1

    # Copy the remaining elements of right[], if any
    while j < len(right):
        arr[k] = right[j]
        j += 1
        k += 1

Explanation

1. Initialization: Create an empty list merged. Set pointers i and j to 0, indicating the current index in left and right, respectively.
2. Compare and Pick:
   • While both i < len(left) and j < len(right), compare left[i] and right[j].
   • Whichever element is smaller, append it to merged and move that pointer forward.
3. Collect Remaining:
   • If any elements remain in left after one of the lists is exhausted, append all of them.
   • Do the same for the remaining elements in right.
4. Result: merged now contains a sorted combination of the two sublists.

Whole Code

class Solution:
 
    def mergeSort(self, arr, l, r):
        if l < r:
            mid = (l + r) // 2
            # Sort first and second halves
            self.mergeSort(arr, l, mid)
            self.mergeSort(arr, mid + 1, r)
            self.merge(arr, l, mid, r)
    
    def merge(self, arr, l, mid, r):
        # Create temp arrays
        left = arr[l:mid+1]
        right = arr[mid+1:r+1]
        
        i = 0
        j = 0
        k = l
        
        # Merge the temp arrays back into arr[l..r]
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1
        
        # Copy the remaining elements of left[], if any
        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1
        
        # Copy the remaining elements of right[], if any
        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1

Also read about the Python Program to Implement Quick Sort Algorithm.

3. Putting It All Together

Initial Array:

arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = merge_sort(arr)
print(f"Sorted array = {sorted_arr}")

Call merge_sort(arr):

1. Splits arr into two halves.
2. Recursively sorts each half.
3. Merges them via merge_array.

Final Output:

Sorted array = [11, 12, 22, 25, 34, 64, 90]

4. Dry Run Example

Let’s dry run a smaller sub-problem: [34, 25, 11].

1. Split:
   • Left: [34]
   • Right: [25, 11]
2. Recursively Sort Left: [34] is a single element, so it’s already sorted.
3. Recursively Sort Right: Split [25, 11] into [25] and [11], both single elements.
   • Merge [25] and [11] → [11, 25].
4. Merge:
   • Merge [34] and [11, 25].
   • Compare 34 with 11 → take 11. Next compare 34 with 25 → take 25. Finally, take 34.
   • Final merged list: [11, 25, 34].

5. Time & Space Complexity

1. Time Complexity:
   • Each time we split the list into two halves and then merge them.
   • The depth of recursion is about log⁡n.
   • At each level, merging all elements takes O(n).
   • Overall time complexity: O(n.log⁡n).
2. Space Complexity:
   • We allocate extra space for the sublists and for merging.
   • Overall space complexity: O(n) in most implementations.

6. Key Takeaways

1. Divide-and-Conquer: Merge Sort systematically splits the array and merges results.
2. Consistent Performance: It guarantees O(nlog⁡n) even in the worst case.
3. Stable Sorting: Merge Sort preserves the order of equal elements, which can be advantageous in certain scenarios.

Requires Extra Space: Unlike in-place sorts, Merge Sort needs additional memory to merge sublists.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.