Merge Sort - CSU083 | Shoolini University

Merge Sort

2025, January 5

1. Prerequisites

Before understanding Merge Sort, you must be familiar with:

2. What is Merge Sort?

Merge Sort is a stable, comparison-based sorting algorithm that follows the divide and conquer paradigm. It splits the array into two halves, recursively sorts each half, and then merges them back together in sorted order.

2.1 Algorithm Steps

  1. Divide the array into two halves recursively until each subarray contains a single element.
  2. Merge the sorted subarrays by comparing elements and arranging them in order.
  3. Continue merging until the entire array is sorted.

2.2 Code Implementation (Python)


def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])

    return merge(left_half, right_half)

def merge(left, right):
    sorted_array = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  
            sorted_array.append(left[i])
            i += 1
        else:
            sorted_array.append(right[j])
            j += 1

    sorted_array.extend(left[i:])
    sorted_array.extend(right[j:])
    
    return sorted_array

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

3. Why Does This Algorithm Exist?

Merge Sort exists because of its efficiency and stability in sorting large datasets. It is widely used in:

4. When Should You Use It?

Merge Sort is the best choice when:

5. How Does It Compare to Alternatives?

5.1 Strengths

5.2 Weaknesses

5.3 Comparison with Other Sorting Algorithms

Algorithm Time Complexity (Best/Average/Worst) Space Complexity Stable? Best Use Case
Merge Sort O(n log n) / O(n log n) / O(n log n) O(n) Yes Large datasets, linked lists, stable sorting
QuickSort O(n log n) / O(n log n) / O(n²) O(log n) (in-place) No General-purpose, when memory is limited
Insertion Sort O(n) / O(n²) / O(n²) O(1) Yes Small datasets, nearly sorted lists
Heap Sort O(n log n) / O(n log n) / O(n log n) O(1) No Priority queues, in-place sorting

6. Basic Implementation

6.1 Python Implementation


def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])

    return merge(left_half, right_half)

def merge(left, right):
    sorted_array = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  
            sorted_array.append(left[i])
            i += 1
        else:
            sorted_array.append(right[j])
            j += 1

    sorted_array.extend(left[i:])
    sorted_array.extend(right[j:])
    
    return sorted_array

# Example Usage
arr = [5, 2, 9, 1, 6]
print("Sorted Array:", merge_sort(arr))

7. Dry Run of Merge Sort

7.1 Input Example

Let's take a small input array: [5, 2, 9, 1, 6]

7.2 Step-by-Step Execution

Step 1: Recursive Division
Step 2: Merging Phase
Merge Step Action Result
Merge [5] and [2] Compare 5 and 2, arrange in order [2, 5]
Merge [1] and [6] Compare 1 and 6, arrange in order [1, 6]
Merge [9] and [1, 6] Compare 9 with 1 and 6, arrange [1, 6, 9]
Merge [2, 5] and [1, 6, 9] Compare elements and merge [1, 2, 5, 6, 9]

7.3 Final Sorted Output

The final sorted array is: [1, 2, 5, 6, 9]

8. Time & Space Complexity Analysis

8.1 Time Complexity Analysis

Merge Sort follows a divide-and-conquer strategy, where an array of size n is:

The recurrence relation for Merge Sort is:

$$ T(n) = 2T(n/2) + O(n) $$

Solving this recurrence using the Master Theorem gives:

8.2 Breakdown of Merge Sort Time Complexity

9. Space Complexity Analysis

9.1 Space Complexity Breakdown

Final Space Complexity: \( O(n) \) (due to extra space for merging).

9.2 Space Complexity Variation

10. Understanding Trade-offs

10.1 Strengths of Merge Sort

10.2 Weaknesses of Merge Sort

10.3 When to Use Merge Sort

10.4 When NOT to Use Merge Sort

11. Optimizations & Variants

11.1 Common Optimizations

Merge Sort can be optimized in several ways to improve performance:

11.2 Variants of Merge Sort

11.3 Optimized Merge Sort Code (Hybrid Approach)

This implementation switches to Insertion Sort for small subarrays.


def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

def merge_sort_optimized(arr):
    if len(arr) <= 10:  # Switch to Insertion Sort for small arrays
        insertion_sort(arr)
        return arr

    mid = len(arr) // 2
    left_half = merge_sort_optimized(arr[:mid])
    right_half = merge_sort_optimized(arr[mid:])

    return merge(left_half, right_half)

arr = [5, 2, 9, 1, 6, 8, 3, 7, 4, 0]
print(merge_sort_optimized(arr))

12. Comparing Iterative vs. Recursive Implementations

12.1 Recursive Merge Sort

12.2 Iterative (Bottom-Up) Merge Sort

12.3 Iterative Merge Sort Code


def iterative_merge_sort(arr):
    n = len(arr)
    width = 1
    while width < n:
        for i in range(0, n, 2 * width):
            left = arr[i:i + width]
            right = arr[i + width:i + 2 * width]
            arr[i:i + 2 * width] = merge(left, right)
        width *= 2
    return arr

arr = [5, 2, 9, 1, 6, 8, 3, 7, 4, 0]
print(iterative_merge_sort(arr))

12.4 When to Use Iterative vs Recursive Merge Sort

Approach Best Used When Key Benefits
Recursive Merge Sort Sorting linked lists or when readability matters Simpler to implement, easy to understand
Iterative Merge Sort Memory is a constraint, and recursion depth is a concern Avoids recursion overhead, better for large arrays

13. Edge Cases & Failure Handling

13.1 Common Pitfalls & Edge Cases

Merge Sort must handle several edge cases to ensure robustness:

14. Writing Test Cases to Verify Correctness

14.1 Test Cases for Merge Sort

These test cases ensure that Merge Sort works correctly across different scenarios.


import unittest

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])

    return merge(left_half, right_half)

def merge(left, right):
    sorted_array = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            sorted_array.append(left[i])
            i += 1
        else:
            sorted_array.append(right[j])
            j += 1

    sorted_array.extend(left[i:])
    sorted_array.extend(right[j:])
    
    return sorted_array

class TestMergeSort(unittest.TestCase):
    def test_empty_array(self):
        self.assertEqual(merge_sort([]), [])

    def test_single_element(self):
        self.assertEqual(merge_sort([5]), [5])

    def test_already_sorted(self):
        self.assertEqual(merge_sort([1, 2, 3, 4, 5]), [1, 2, 3, 4, 5])

    def test_reverse_sorted(self):
        self.assertEqual(merge_sort([5, 4, 3, 2, 1]), [1, 2, 3, 4, 5])

    def test_duplicates(self):
        self.assertEqual(merge_sort([4, 2, 2, 4, 1, 1]), [1, 1, 2, 2, 4, 4])

    def test_negative_numbers(self):
        self.assertEqual(merge_sort([-3, -1, -4, 2, 0, 1]), [-4, -3, -1, 0, 1, 2])

    def test_large_input(self):
        import random
        arr = [random.randint(0, 1000) for _ in range(1000)]
        self.assertEqual(merge_sort(arr), sorted(arr))

if __name__ == '__main__':
    unittest.main()

15. Understanding Real-World Failure Scenarios

15.1 Possible Failures in Practical Applications

15.2 Mitigating These Issues

16. Real-World Applications & Industry Use Cases

16.1 How is Merge Sort Used in Real-World Applications?

Merge Sort is widely used in industry due to its efficiency and stability, especially in scenarios involving large datasets.

17. Open-Source Implementations of Merge Sort

17.1 Open-Source Implementations in Popular Libraries

Merge Sort is implemented in several open-source projects:

17.2 Sample Merge Sort Implementation from Open Source

A C++ implementation of Merge Sort from the GNU Coreutils project:


void mergeSort(vector& arr, int left, int right) {
    if (left >= right) return;

    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);

    merge(arr, left, mid, right);
}

18. Practical Project: Sorting Large Text Files

18.1 Project Idea: Implement a File Sorter for Large Datasets

This script sorts a large text file containing numbers using Merge Sort.

18.2 Python Script for Sorting Large Files


import heapq

def merge_sort_files(input_file, output_file, chunk_size=10000):
    """Sorts a large file using Merge Sort with external sorting."""
    
    chunks = []
    with open(input_file, 'r') as f:
        while True:
            lines = f.readlines(chunk_size)
            if not lines:
                break
            numbers = list(map(int, lines))
            numbers.sort()
            chunk_file = f'chunk_{len(chunks)}.txt'
            with open(chunk_file, 'w') as chunk:
                chunk.write('\n'.join(map(str, numbers)))
            chunks.append(chunk_file)

    with open(output_file, 'w') as out:
        files = [open(chunk, 'r') for chunk in chunks]
        iterators = [map(int, f) for f in files]
        for number in heapq.merge(*iterators):
            out.write(str(number) + '\n')

    for f in files:
        f.close()

# Usage
merge_sort_files('large_numbers.txt', 'sorted_numbers.txt')

18.3 Explanation

18.4 Use Cases

19. Competitive Programming & System Design Integration

19.1 Merge Sort in Competitive Programming

Merge Sort is commonly used in coding competitions for problems requiring:

19.2 Merge Sort in System Design

In large-scale systems, Merge Sort is often used for:

19.3 Optimized Merge Sort for Distributed Systems


from multiprocessing import Pool

def merge_sort_parallel(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2

    with Pool(2) as p:
        left_half, right_half = p.map(merge_sort_parallel, [arr[:mid], arr[mid:]])

    return merge(left_half, right_half)

arr = [10, 7, 8, 9, 1, 5]
sorted_arr = merge_sort_parallel(arr)
print(sorted_arr)

20. Assignments

20.1 Solve at least 10 problems using Merge Sort

Practice these problems to gain confidence in implementing Merge Sort.

20.2 Use Merge Sort in a System Design Problem

Design a large-scale log processing system that:

20.3 Practice Implementing Under Time Constraints

Set a timer and try implementing Merge Sort within: