Sorting Algorithms Compared: Bubble, Merge, Quick, Heap

Sorting data is one of the most fundamental operations in computer science. Whether organizing search results by relevance, ordering financial transactions by timestamp, or optimizing search algorithms, choosing the right sorting technique dictates system performance.

Different sorting algorithms offer distinct trade-offs regarding time complexity, memory overhead, and stability. This comprehensive guide compares four core sorting algorithms—**Bubble Sort**, **Merge Sort**, **Quick Sort**, and **Heap Sort**—accompanied by performance benchmarks and clean **Python** implementations.

1. Performance Summary Table

Before diving into individual implementations, here is how the four algorithms compare across time complexities and stability:

• Bubble Sort: Time Complexity O(n^2) Average/Worst, O(n) Best. Space Complexity O(1). Stable.
• Merge Sort: Time Complexity O(n log n) across Best, Average, and Worst. Space Complexity O(n). Stable.
• Quick Sort: Time Complexity O(n log n) Average/Best, O(n^2) Worst. Space Complexity O(log n). Unstable.
• Heap Sort: Time Complexity O(n log n) across Best, Average, and Worst. Space Complexity O(1). Unstable.

2. Bubble Sort: The Intuitive Educational Sort

**Bubble Sort** is the simplest sorting algorithm, repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order.

def bubble_sort(arr: list) -> list:
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

3. Merge Sort: Divide and Conquer Stability

**Merge Sort** follows a strict divide-and-conquer paradigm. It recursively splits the array into halves until each sub-array contains a single element, then merges them back together in sorted order.

def merge_sort(arr: list) -> list:
    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: list, right: list) -> list:
    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

4. Quick Sort: Fast In-Place Partitioning

**Quick Sort** is generally the fastest in-practice comparison sort. It selects a 'pivot' element, partitions the array into elements smaller and larger than the pivot, and recursively sorts the sub-arrays.

def quick_sort(arr: list) -> list:
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

5. Heap Sort: Guaranteed O(n log n) with O(1) Space

**Heap Sort** leverages a binary heap data structure. It transforms the array into a max-heap, repeatedly extracts the maximum element, and places it at the end of the array.

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: list) -> list:
    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[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    return arr

Conclusion

Choosing the correct sorting algorithm depends on your memory and speed constraints. Use **Quick Sort** for general high-speed sorting, **Merge Sort** when stability and guaranteed O(n log n) performance are required, and **Heap Sort** when operating under strict O(1) auxiliary memory limits.