Back to Arrays & Sorting

Merge Sort

Merge Sort is a guaranteed $O(n \log n)$ Divide-and-Conquer algorithm. It breaks down a problem into smaller sub-problems recursively, solves them, and merges the results back together.

         The Divide & Conquer Strategy:
        Divide: Find the midpoint and split the array into two halves.
Conquer: Recursively sort both sub-arrays.

            Combine (Merge): Merge the two sorted halves into a single sorted array
            by taking the smaller element from the front of each half.

Python Implementation

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        # Recursive calls
        merge_sort(left_half)
        merge_sort(right_half)

        # Merge process
        i = j = k = 0
        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 for remaining elements
        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

Complexity Analysis

Best, Average & Worst Case Time: $O(n \log n)$ — guaranteed, regardless of initial element arrangement.
Space Complexity: $O(n)$ — requires extra memory for auxiliary sub-arrays during merging.
Stability: Stable (Preserves relative ordering of equal elements).