Merge Sort

Overview

Merge Sort is a highly efficient, comparison-based sorting algorithm that uses the divide-and-conquer approach. It divides the input array into smaller sub-arrays, sorts them recursively, and then merges the sorted sub-arrays back together. Merge Sort is particularly effective for large data sets and ensures a consistently good performance.

How Merge Sort Works

• Divide: Split the array into two halves.
• Conquer: Recursively sort each half.
• Merge: Combine the two sorted halves into a single sorted array.

Properties of Merge Sort

• Stable: Maintains the relative order of equal elements.
• Time Complexity:
  • Best, Worst, and Average Case: O(n log n).
• Space Complexity:
  • Requires additional memory for temporary arrays (O(n)).

Steps of Merge Sort

Given an unsorted list:

38, 27, 43, 3, 9, 82, 10

Step 1: Split the list recursively until each sublist has one element.

38, 27, 43, 3, 9, 82, 10 → 38, 27, 43, 3, 9, 82, 10

→ 38, 27, 43, 3, 9, 82, 10

→ 38, 27, 43, 3, 9, 82, 10

Step 2: Merge pairs of sublists in sorted order.

27, 38, 3, 43, 9, 82, 10

Step 3: Merge again.

3, 27, 38, 43, 9, 10, 82

Step 4: Final merge to get the sorted list.

3, 9, 10, 27, 38, 43, 82

Pseudocode for Merge Sort

Merge Sort:

METHOD MergeSort(array)
    IF array.length > 1
        mid ← array.length DIV 2
        left ← array[0 TO mid - 1]
        right ← array[mid TO array.length - 1]

        CALL MergeSort(left)
        CALL MergeSort(right)

        CALL Merge(left, right, array)

Merge:

METHOD Merge(left, right, array)
    i ← 0  // Index for left subarray
    j ← 0  // Index for right subarray
    k ← 0  // Index for merged array

    WHILE i < left.length AND j < right.length
        IF left[i] ≤ right[j]
            array[k] ← left[i]
            i ← i + 1
        ELSE
            array[k] ← right[j]
            j ← j + 1
        k ← k + 1

    WHILE i < left.length
        array[k] ← left[i]
        i ← i + 1
        k ← k + 1

    WHILE j < right.length
        array[k] ← right[j]
        j ← j + 1
        k ← k + 1

Python Example

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

        # Recursively sort both halves
        merge_sort(left_half)
        merge_sort(right_half)

        # Merge sorted halves
        i = j = k = 0
        while i < len(left_half) and j < len(right_half):
            if left_half[i] <= right_half[j]:
                array[k] = left_half[i]
                i += 1
            else:
                array[k] = right_half[j]
                j += 1
            k += 1

        # Copy any remaining elements in left_half
        while i < len(left_half):
            array[k] = left_half[i]
            i += 1
            k += 1

        # Copy any remaining elements in right_half
        while j < len(right_half):
            array[k] = right_half[j]
            j += 1
            k += 1

# Example usage:
data = [38, 27, 43, 3, 9, 82, 10]
merge_sort(data)
print(data)  # Output: [3, 9, 10, 27, 38, 43, 82]

Tracing Merge Sort

Note Summary