Merge Sort

Merge Sort is a divide-and-conquer sorting algorithm that recursively splits an array into smaller subarrays, sorts them, and then merges the sorted subarrays to produce the final sorted array. It guarantees a worst-case time complexity of O(n log n).

Algorithm Overview

Merge Sort follows these steps:

Divide: Recursively split the array into two halves until each subarray has one element.
Conquer: Sort the subarrays (trivial for single-element arrays).
Merge: Combine the sorted subarrays into a single sorted array.

Example

Sorting [38, 27, 43, 3, 9, 82, 10] using Merge Sort:

Split: [38, 27, 43, 3] and [9, 82, 10]
Split further: [38, 27], [43, 3], [9, 82], [10]
Base case: Single elements remain → Merge back:
- Merge [38] and [27] → [27, 38]
- Merge [43] and [3] → [3, 43]
- Merge [9] and [82] → [9, 82]
- Merge [27, 38] and [3, 43] → [3, 27, 38, 43]
- Merge [9, 82] and [10] → [9, 10, 82]
- Merge [3, 27, 38, 43] and [9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]

Implementation

A simple implementation of Merge Sort in Python:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    sorted_list = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_list.append(left[i])
            i += 1
        else:
            sorted_list.append(right[j])
            j += 1
    sorted_list.extend(left[i:])
    sorted_list.extend(right[j:])
    return sorted_list

arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr))

Time Complexity

Merge Sort has a time complexity of:

Best case: O(n log n) (Even if already sorted, it still splits and merges)
Average case: O(n log n)
Worst case: O(n log n) (Fully reversed array)

Space Complexity

O(n) – Requires additional space to store subarrays during merging.

Comparison with Other Sorting Algorithms

Algorithm	Time Complexity (Worst)	Space Complexity	Stable	In-Place
Merge Sort	O(n log n)	O(n)	Yes	No
Quick Sort	O(n²)	O(log n)	No	Yes
Bubble Sort	O(n²)	O(1)	Yes	Yes
Heap Sort	O(n log n)	O(1)	No	Yes

Advantages

Stable Sorting Algorithm: Maintains relative order of equal elements.
Guaranteed O(n log n) Complexity: Unlike Quick Sort, it does not degrade to O(n²).
Efficient for Linked Lists: Unlike array-based sorting, linked lists benefit from its merging process.

Limitations

Not In-Place: Requires additional memory for merging subarrays.
Slower for Small Datasets: Algorithms like Insertion Sort can be faster for small n.

Applications

Sorting large datasets where stability is required.
External sorting when data is too large to fit into memory.
Merging linked lists efficiently.