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:

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

Example

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

1. Split: [38, 27, 43, 3] and [9, 82, 10]
2. Split further: [38, 27], [43, 3], [9, 82], [10]
3. 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.

See Also

• Sorting Algorithm
• Quick Sort
• Heap Sort
• Divide-and-Conquer Algorithm
• Time Complexity
• Stable Sorting