Tag: Big-O complexity

Sorting isn't just an academic problem—choosing the right algorithm can impact real-world system performance, especially when working with large datasets or latency-sensitive applications. In this post, you'll see how QuickSort, MergeSort, and TimSort stack up: you'll get Big-O complexity, walk through step-by-step execution on a realistic array, and see actual benchmark numbers for arrays of 1,000, 10,000, and 100,000 elements.

Key Takeaways:

• Understand the practical differences between QuickSort, MergeSort, and TimSort—including real-world speed and memory use
• See step-by-step execution, not just code
• Get Big-O time/space complexity for each algorithm
• View realistic Python benchmarks for 1K, 10K, and 100K element arrays
• Learn which sorting algorithm to use for your data and why

Prerequisites

• Python 3.8+ installed (download here)
• Basic familiarity with Python lists and functions
• NumPy installed for generating large random arrays:

  pip install numpy

• Understanding of basic time complexities (Big-O notation) is helpful, but not required

Algorithm Overview and Big-O Comparison

Let's summarize the core features, time complexities, and space usage for each sorting algorithm:

QuickSort is usually fastest in practice, but can degrade to O(n²) on already sorted or adversarial data. MergeSort has predictable performance regardless of input, but uses more memory. TimSort (used in Python's sorted() and Java's Arrays.sort for objects) combines MergeSort and Insertion Sort, exploiting existing order in the data for optimal speed.

For further reading, see the official Python Sorting HOWTO.

Step-by-Step Execution on a Sample Array

Let’s step through sorting the array [10, 7, 8, 9, 1, 5] using each algorithm.

QuickSort (Lomuto partition, in-place)

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

def partition(arr, low, high):
    pivot = arr[high] # Choose last element as pivot
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i] # Swap
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

A = [10, 7, 8, 9, 1, 5]
quicksort(A, 0, len(A) - 1)
print(A) # [1, 5, 7, 8, 9, 10]

• Step 1: Pivot is 5. Partition: [1, 5, 8, 9, 10, 7] → after swaps: [1, 5, 8, 9, 10, 7]
• Step 2: Recursively sort subarrays left and right of pivot (index 1)
• Final: Array is sorted in-place

Why it matters: QuickSort is fast and in-place, but unstable. Pivot choice is crucial for performance.

MergeSort (out-of-place, stable)

def mergesort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]
        mergesort(L)
        mergesort(R)
        i = j = k = 0
        # Merge L and R
        while i < len(L) and j < len(R):
            if L[i] <= R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
        # Remaining elements
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

B = [10, 7, 8, 9, 1, 5]
mergesort(B)
print(B) # [1, 5, 7, 8, 9, 10]

• Step 1: Split array into [10,7,8] and [9,1,5]
• Step 2: Recursively split and merge; e.g., [10,7,8] → [10],[7],[8] → merge to [7,8,10]
• Step 3: Merge sorted halves: [7,8,10] and [1,5,9] → [1,5,7,8,9,10]

Why it matters: MergeSort is stable and always O(n log n), but needs extra memory.

TimSort (Python’s built-in, hybrid, stable)

C = [10, 7, 8, 9, 1, 5]
C_sorted = sorted(C) # Uses TimSort internally in Python 3.x
print(C_sorted) # [1, 5, 7, 8, 9, 10]

• Step 1: TimSort identifies ordered runs (contiguous sorted subsequences)
• Step 2: Uses insertion sort on small runs, then merges them using MergeSort logic
• Step 3: Final sorted array is stable and efficient, especially for partially ordered data

Why it matters: TimSort is the default in Python and Java for a reason—it's very fast for real-world, partially sorted data.

Benchmarking Sorting Performance

Let’s benchmark all three algorithms using realistic data sizes. We'll use NumPy to generate random arrays and time.perf_counter() for accurate timing.

import numpy as np
import time

def quicksort_py(arr):
    # Helper wrapper to match list.copy() interface
    def quicksort_inner(arr, low, high):
        if low < high:
            pi = partition(arr, low, high)
            quicksort_inner(arr, low, pi - 1)
            quicksort_inner(arr, pi + 1, high)
    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
    arr = arr.copy()
    quicksort_inner(arr, 0, len(arr) - 1)
    return arr

def mergesort_py(arr):
    arr = arr.copy()
    def mergesort_inner(arr):
        if len(arr) > 1:
            mid = len(arr) // 2
            L = arr[:mid]
            R = arr[mid:]
            mergesort_inner(L)
            mergesort_inner(R)
            i = j = k = 0
            while i < len(L) and j < len(R):
                if L[i] <= R[j]:
                    arr[k] = L[i]
                    i += 1
                else:
                    arr[k] = R[j]
                    j += 1
                k += 1
            while i < len(L):
                arr[k] = L[i]
                i += 1
                k += 1
            while j < len(R):
                arr[k] = R[j]
                j += 1
                k += 1
    mergesort_inner(arr)
    return arr

def timsort_py(arr):
    return sorted(arr)

for size in [1000, 10000, 100000]:
    arr = np.random.randint(0, 1000000, size).tolist()
    for sort_name, sort_func in [
        ("QuickSort", quicksort_py),
        ("MergeSort", mergesort_py),
        ("TimSort", timsort_py)
    ]:
        start = time.perf_counter()
        sort_func(arr)
        duration = time.perf_counter() - start
        print(f"{sort_name} - {size} elements: {duration:.4f} seconds")

Sample output on a modern laptop (Python 3.10, Intel i7):

QuickSort - 1000 elements: 0.0082 seconds
MergeSort - 1000 elements: 0.0183 seconds
TimSort - 1000 elements: 0.0005 seconds
QuickSort - 10000 elements: 0.0957 seconds
MergeSort - 10000 elements: 0.1824 seconds
TimSort - 10000 elements: 0.0041 seconds
QuickSort - 100000 elements: 1.1612 seconds
MergeSort - 100000 elements: 2.0329 seconds
TimSort - 100000 elements: 0.0407 seconds

What this shows: TimSort (Python built-in) is orders of magnitude faster than naive Python implementations of QuickSort and MergeSort. For production, always use built-in or library implementations, not hand-rolled versions.

Note: C implementations (C++ std::sort, Java Arrays.sort, etc.) will be faster than pure Python versions. This benchmark illustrates algorithmic differences, not absolute speeds.

Common Pitfalls and Pro Tips

QuickSort Pitfalls

• Worst-case O(n²): Happens if the pivot is always the smallest/largest element (e.g., already sorted arrays). Use random pivot selection or "median-of-three" to mitigate.
• Unstable: Equal elements may not retain original order. Not suitable for sorting objects where stability matters (e.g., multi-key sorting).
• Stack overflow: Recursion depth may be exceeded for large arrays. Use iterative QuickSort or tail recursion optimization in production.

MergeSort Pitfalls

• Extra memory: Requires O(n) additional space. Can be a problem for very large datasets or memory-constrained environments.
• No in-place support: Standard MergeSort copies subarrays. In-place versions exist but are complex and rarely used.

TimSort Pro Tips

• Best for real-world data: TimSort is optimized for partially ordered data. If your data is nearly sorted, TimSort can be O(n) in practice.
• Stability: Guarantees equal elements retain their order. Essential for sorting complex objects by multiple keys.
• Use the built-in: Writing your own sort is nearly always slower and less reliable than using sorted() or list.sort() in Python (both use TimSort).

Conclusion and Next Steps

Pick QuickSort for general use when you control the pivot strategy and stability isn't required. Use MergeSort when you need stable, predictable O(n log n) performance and can spare the memory. For Python, or when working with partially sorted or complex data, TimSort (via sorted()) is almost always the best choice.

Next, try benchmarking with real datasets from your own applications or explore parallel sort algorithms for even larger arrays. For more on sorting, see the Sorting Algorithm Wikipedia page or the Python Sorting HOWTO.