Merge Sort

About

Merge Sort breaks a big sorting problem down into microscopic, easy-to-solve pieces using a recursive strategy.

1. Divide: It keeps cutting the array in half until it is completely broken down into single-element subarrays (which are inherently sorted).
   
   
2. Conquer: It zips those small pieces back together in pairs. When merging two sorted pieces, it compares their front-most elements, takes the smaller one, and builds a perfectly combined, sorted array, working its way all the way back up to the top.

![[mer.mp4]]

Complexities

• Time complexity:

  • Best / Average / Worst Case: $O(n\log n)$

  Why it's so consistent: The algorithm splits the array in half at every level, creating a balanced binary tree structure of height $\log n$. At every single level of that tree, it does $O(n)$ work combining elements. Since the tree structure behaves exactly the same way regardless of the data arrangement, it guaranteed to execute in $O(n\log n)$ time even in the absolute worst-case scenario.

• Space complexity: $O(n)$

Code Implementation

def merge_sort(arr):
    # Base case: A single element or empty array is already sorted
    if len(arr) <= 1:
        return arr
        
    # Find the middle point to split the array
    mid = len(arr) // 2
    
    # Recursively split and sort the left and right halves
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])
    
    # Merge the sorted halves back together
    return merge(left_half, right_half)


def merge(left, right):
    sorted_arr = []
    i = j = 0  # Pointers for tracking indices in left and right lists
    
    # Compare elements from both lists and assemble them in order
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # The '<=' ensures stability
            sorted_arr.append(left[i])
            i += 1
        else:
            sorted_arr.append(right[j])
            j += 1
            
    # Gather any remaining elements left over from either array
    sorted_arr.extend(left[i:])
    sorted_arr.extend(right[j:])
    
    return sorted_arr

Key Takeaways

• The Space Trade-off: Its biggest downside is memory. While algorithms like Quick Sort sort the data in-place ($O(1)$ auxiliary space), Merge Sort requires an extra clone of the dataset ($O(n)$ space) to perform the zipping phase.
  
  
• Perfect for Linked Lists: Merge Sort is the absolute best choice for sorting a Linked List. Because linked list nodes are scattered across random memory locations, you can't easily swap values by an index (like in Quick Sort). However, you can easily change node pointers to split and merge them without consuming $O(n)$ extra memory!
  
  
• When to Use It:
  • Used heavily when predictable, stable sorting performance is critical.
    
    
  • Excellent for processing massive datasets that cannot fit entirely into external system RAM (a concept known as External Sorting), where data is broken down into small blocks, sorted individually, and streamed together via a merge.