Comparing Advanced Sorting Algorithms

In the previous article, we explored two advanced sorting algorithms—bucket sort and radix sort—examining how each works and their respective use cases. In this article, we focus on comparing several more sophisticated sorting algorithms: merge sort, heap sort, and quick sort. These algorithms hold significant practical importance—especially when handling large-scale datasets.

Merge Sort

Overview

Merge sort is a divide-and-conquer algorithm. Its core idea is to recursively split an array into two halves, sort each half independently, and then merge the two sorted halves into a single sorted array.

Algorithm Steps

1. Divide: Split the array into two approximately equal halves.
2. Conquer (Recursion): Recursively apply merge sort to both subarrays.
3. Combine (Merge): Merge the two sorted subarrays into one final sorted array.

Complexity Analysis

Merge sort has a time complexity of $O(n \log n)$ and a space complexity of $O(n)$, as auxiliary storage is required during the merging phase. Its stability—i.e., preservation of relative order among equal elements—makes it preferable in certain applications.

Code Example

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

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

Heap Sort

Overview

Heap sort leverages the binary heap data structure to sort an array. It proceeds in two phases: first constructing a max-heap from the input array, then repeatedly extracting the maximum element (at the root), placing it at the end of the array, and restoring the heap property.

Algorithm Steps

1. Build Max-Heap: Transform the unsorted array into a max-heap.
2. Extract & Restore: Swap the root (largest remaining element) with the last element in the current heap segment, reduce the heap size by one, and re-heapify the reduced segment.

Complexity Analysis

Heap sort runs in $O(n \log n)$ time and uses only $O(1)$ extra space—it is an in-place sorting algorithm, requiring no additional memory proportional to input size.

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

Quick Sort

Overview

Quick sort is also a divide-and-conquer algorithm. It selects a pivot element and partitions the array such that all elements less than the pivot appear to its left, and all elements greater than the pivot appear to its right.

Algorithm Steps

1. Choose Pivot: Select an element from the array as the pivot.
2. Partition: Rearrange the array so that elements smaller than the pivot lie to its left, and larger elements lie to its right.
3. Recursion: Recursively apply quick sort to the left and right subarrays.

Complexity Analysis

Quick sort has an average-case time complexity of $O(n \log n)$. However, in the worst case—e.g., when the input is already sorted or nearly sorted—its time complexity degrades to $O(n^2)$. Its space complexity is $O(\log n)$ due to recursion stack depth, and in practice, it often outperforms other $O(n \log n)$ algorithms thanks to excellent cache locality and low constant factors.

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)

Summary

In this article, we examined three advanced sorting algorithms—merge sort, heap sort, and quick sort—in depth. Each possesses distinct characteristics and trade-offs, making the choice of algorithm critical for optimizing program performance. In the next article, we will shift our focus to graph algorithms, diving into Dijkstra’s algorithm and the A* algorithm, exploring their significance and practical applications in pathfinding.