Merge Sort, Quick Sort & Heap Sort

1. Merge Sort

Merge Sort is a classic divide-and-conquer sorting algorithm that divides the array into halves, recursively sorts them, and then merges the sorted halves.

How Merge Sort Works

Python Code Example

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

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

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

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)

2. Quick Sort

Quick Sort is an efficient in-place sorting algorithm that uses partitioning to divide the array and recursively sort the partitions.

How Quick Sort Works

Python Code Example

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

3. Heap Sort

Heap Sort uses a binary heap data structure to efficiently sort an array by repeatedly extracting the maximum element.

How Heap Sort Works

Python Code Example

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

Comparison of Merge Sort, Quick Sort & Heap Sort

Algorithm Time Complexity (Best) Time Complexity (Average) Time Complexity (Worst) Space Complexity Stability Use Case
Merge Sort O(n log n) O(n log n) O(n log n) O(n) Stable Linked lists, stable sorting
Quick Sort O(n log n) O(n log n) O(n²) O(log n) recursive stack Not stable General-purpose in-memory sort
Heap Sort O(n log n) O(n log n) O(n log n) O(1) Not stable Memory constrained environments