Sorting Algorithms Face-Off: From Bubble Sort to Quick Sort¶

Seven sorting algorithms walk into a bar. The bartender says, “I’ll serve you in order.” Bubble Sort says, “Give me a few hours.” Quick Sort says, “I’ll have everyone seated in O(n log n).” Counting Sort says, “Hold my beer, I don’t even need to compare.”

Sorting is one of the most fundamental operations in computer science. It sounds boring, and honestly, as a standalone task, it kind of is. But virtually every non-trivial application depends on sorting in some way:

• Databases sort records for indexed queries and ORDER BY clauses
• Search engines sort results by relevance
• Operating systems sort files by name, date, or size
• Graphics engines sort objects by depth for rendering
• Scheduling systems sort tasks by priority

Beyond direct use, sorting is a gateway to understanding algorithm design, divide-and-conquer strategies, and the trade-offs between time, space, and implementation complexity. It is also the topic most likely to appear on a whiteboard interview, so there is that.

Today, we are putting seven algorithms head-to-head. Each one gets a step-by-step visualization, a Python implementation, a complexity analysis, and an honest assessment of when you should (or should never) use it. Let’s find out who wins.

Before We Start: Key Concepts¶

Stability: A sorting algorithm is stable if it preserves the relative order of elements with equal keys. For example, if you sort students by grade and two students both have an “A,” a stable sort keeps them in their original order relative to each other. This matters more than you think, especially when sorting by multiple criteria.

In-place: An algorithm is in-place if it uses O(1) extra memory (besides the input array). It sorts by rearranging elements within the array rather than creating a new one. Your memory-constrained embedded system cares about this a lot.

Comparison-based: Most sorting algorithms work by comparing pairs of elements. The theoretical lower bound for comparison-based sorting is O(n log n). You literally cannot go faster using only comparisons. Non-comparison sorts (like Counting Sort) can beat this bound under specific conditions, but they have their own trade-offs.

Contestant #1: Bubble Sort: The Lovable Underdog¶

“I’m not fast, but I’m honest.”

How It Works¶

Bubble Sort is the algorithm you learn first and use never. It repeatedly walks through the list, compares adjacent elements, and swaps them if they are in the wrong order. Larger elements “bubble up” to the end of the list with each pass, like bubbles rising in a soda. The algorithm keeps repeating until no swaps are needed.

Step-by-Step on [5, 3, 8, 1, 2]¶

Pass 1:

[5, 3, 8, 1, 2]  Compare 5 and 3 -> swap
[3, 5, 8, 1, 2]  Compare 5 and 8 -> no swap
[3, 5, 8, 1, 2]  Compare 8 and 1 -> swap
[3, 5, 1, 8, 2]  Compare 8 and 2 -> swap
[3, 5, 1, 2, 8]  <- 8 is now in its final position

Pass 2:

[3, 5, 1, 2, 8]  Compare 3 and 5 -> no swap
[3, 5, 1, 2, 8]  Compare 5 and 1 -> swap
[3, 1, 5, 2, 8]  Compare 5 and 2 -> swap
[3, 1, 2, 5, 8]  <- 5 is now in its final position

Pass 3:

[3, 1, 2, 5, 8]  Compare 3 and 1 -> swap
[1, 3, 2, 5, 8]  Compare 3 and 2 -> swap
[1, 2, 3, 5, 8]  <- 3 is now in its final position

Pass 4:

[1, 2, 3, 5, 8]  Compare 1 and 2 -> no swap
[1, 2, 3, 5, 8]  <- No swaps, array is sorted!

Python Implementation¶

def bubble_sort(arr):
    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
        # Optimization: if no swaps occurred, array is already sorted
        if not swapped:
            break
    return arr

# Test
data = [5, 3, 8, 1, 2]
print(bubble_sort(data))  # [1, 2, 3, 5, 8]

Complexity¶

• Best case: O(n), when the array is already sorted (with the swapped optimization)
• Average case: O(n^2)
• Worst case: O(n^2), when the array is sorted in reverse
• Space: O(1), in-place
• Stable: Yes

The Verdict¶

Almost never use Bubble Sort in production. It is the participation trophy of sorting algorithms. Its only advantages are extreme simplicity and the ability to detect an already-sorted array in O(n). Its primary purpose in life is teaching beginners what NOT to do at scale.

Contestant #2: Selection Sort: The Methodical Minimalist¶

“I find the smallest, I put it first. Repeat. Simple.”

How It Works¶

Selection Sort divides the array into two parts: a sorted portion (on the left) and an unsorted portion (on the right). It repeatedly finds the minimum element from the unsorted portion and places it at the end of the sorted portion. Think of it as going through a messy pile of papers and repeatedly pulling out the one with the lowest number.

Step-by-Step on [29, 10, 14, 37, 13]¶

[29, 10, 14, 37, 13]  Find min in [29,10,14,37,13] -> 10 at index 1
 ^min found                Swap arr[0] and arr[1]
[10, 29, 14, 37, 13]  Find min in [29,14,37,13] -> 13 at index 4
     ^                     Swap arr[1] and arr[4]
[10, 13, 14, 37, 29]  Find min in [14,37,29] -> 14 at index 2
         ^                 Already in position, no swap needed
[10, 13, 14, 37, 29]  Find min in [37,29] -> 29 at index 4
             ^             Swap arr[3] and arr[4]
[10, 13, 14, 29, 37]  Done!

Python Implementation¶

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # Find the minimum element in the unsorted portion
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # Swap the found minimum with the first unsorted element
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# Test
data = [29, 10, 14, 37, 13]
print(selection_sort(data))  # [10, 13, 14, 29, 37]

Complexity¶

• Best case: O(n^2), always scans the entire unsorted portion, even if already sorted
• Average case: O(n^2)
• Worst case: O(n^2)
• Space: O(1), in-place
• Stable: No, swapping can change the relative order of equal elements

The Verdict¶

Selection Sort has one niche: when the number of writes must be minimized. It makes at most n-1 swaps, which can matter when writing to memory is expensive (like flash storage that wears out with writes). Other than that, it is consistently slow and not even stable. It is the “reliable but uninspiring” choice.

Contestant #3: Insertion Sort: The Card Player’s Favorite¶

“I sort like you sort cards in your hand. You already do this. You just didn’t know it had a name.”

How It Works¶

Insertion Sort builds the sorted array one element at a time. It takes each element from the unsorted portion and inserts it into its correct position within the sorted portion, shifting elements as needed. If you have ever picked up a hand of cards and arranged them from left to right, congratulations, you have performed Insertion Sort.

Step-by-Step on [7, 4, 5, 2, 9]¶

Initial: [7, 4, 5, 2, 9]
         sorted|unsorted

Step 1: Take 4, insert into [7]
        4 < 7, shift 7 right, place 4
        [4, 7, 5, 2, 9]

Step 2: Take 5, insert into [4, 7]
        5 < 7, shift 7 right
        5 > 4, place 5
        [4, 5, 7, 2, 9]

Step 3: Take 2, insert into [4, 5, 7]
        2 < 7, shift 7 right
        2 < 5, shift 5 right
        2 < 4, shift 4 right
        Place 2 at start
        [2, 4, 5, 7, 9]

Step 4: Take 9, insert into [2, 4, 5, 7]
        9 > 7, place 9 at end
        [2, 4, 5, 7, 9]  Done!

Python Implementation¶

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]           # The element to insert
        j = i - 1

        # Shift elements that are greater than key to the right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key      # Insert the element at its correct position
    return arr

# Test
data = [7, 4, 5, 2, 9]
print(insertion_sort(data))  # [2, 4, 5, 7, 9]

Complexity¶

• Best case: O(n), when the array is already sorted (inner loop never executes)
• Average case: O(n^2)
• Worst case: O(n^2), when the array is sorted in reverse
• Space: O(1), in-place
• Stable: Yes

The Verdict¶

Do not underestimate Insertion Sort. Yes, it is O(n^2) in the worst case. But it has several tricks up its sleeve:

• Small arrays (n < 50): The low overhead makes it faster than Merge Sort or Quick Sort for small inputs. Less recursion overhead, fewer function calls, better cache performance.
• Nearly sorted data: It runs in nearly O(n) time when the input is almost sorted. Most real-world data has some order to it.
• Online sorting: It can sort a list as it receives elements one by one.
• Sub-routine in hybrid algorithms: TimSort (Python) and IntroSort (C++) both switch to Insertion Sort for small partitions.

Insertion Sort is like a reliable station wagon, it won’t win any races, but it’s perfect for the grocery run.

Why does Insertion Sort make a great party guest? Because it always knows exactly where to fit in!

Contestant #4: Merge Sort: The Reliable Overachiever¶

“I guarantee O(n log n). Every. Single. Time. No exceptions.”

How It Works¶

Merge Sort follows the divide-and-conquer paradigm:
1. Divide the array into two halves
2. Recursively sort each half
3. Merge the two sorted halves into a single sorted array

The key insight: merging two already-sorted arrays is trivially easy, just compare the front elements and take the smaller one. Repeat until done. O(n) for the merge, log n levels of recursion, total: O(n log n). Every time.

Step-by-Step on [38, 27, 43, 3, 9, 82, 10]¶

Splitting Phase:

                [38, 27, 43, 3, 9, 82, 10]
               /                           \
        [38, 27, 43]                  [3, 9, 82, 10]
        /         \                   /            \
    [38]      [27, 43]          [3, 9]        [82, 10]
              /      \          /     \        /      \
           [27]     [43]     [3]     [9]   [82]     [10]

Merging Phase (bottom-up):

           [27]     [43]     [3]     [9]   [82]     [10]
              \      /          \     /        \      /
           [27, 43]            [3, 9]        [10, 82]
        \         /                   \            /
     [27, 38, 43]                  [3, 9, 10, 82]
               \                           /
            [3, 9, 10, 27, 38, 43, 82]

Merge example: merging [27, 38, 43] and [3, 9, 10, 82]:

Left:  [27, 38, 43]    Right: [3, 9, 10, 82]    Result: []
        ^                      ^
Compare 27 vs 3 -> take 3                        Result: [3]
Compare 27 vs 9 -> take 9                        Result: [3, 9]
Compare 27 vs 10 -> take 10                      Result: [3, 9, 10]
Compare 27 vs 82 -> take 27                      Result: [3, 9, 10, 27]
Compare 38 vs 82 -> take 38                      Result: [3, 9, 10, 27, 38]
Compare 43 vs 82 -> take 43                      Result: [3, 9, 10, 27, 38, 43]
Take remaining 82                                Result: [3, 9, 10, 27, 38, 43, 82]

Python Implementation¶

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)
def merge(left, right):
    result = []
    i = j = 0

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

    # Append any remaining elements
    result.extend(left[i:])
    result.extend(right[j:])
    return result
# Test
data = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(data))  # [3, 9, 10, 27, 38, 43, 82]

Complexity¶

• Best case: O(n log n)
• Average case: O(n log n)
• Worst case: O(n log n), guaranteed, unlike Quick Sort
• Space: O(n), requires additional space for the temporary arrays
• Stable: Yes

The Verdict¶

Merge Sort is the “boring but correct” choice. It guarantees O(n log n) no matter what you throw at it. No worst-case degradation, no pathological inputs, no surprises. The trade-off is O(n) extra space, it cannot sort in-place. Use it when:

• You need guaranteed O(n log n) performance (no O(n^2) surprises)
• Stability is required
• You are sorting linked lists (Merge Sort is perfect for linked lists since no random access is needed)
• Your data is too large for memory (external sorting, merge sorted chunks from disk)

Contestant #5: Quick Sort: The Crowd Favorite¶

“I’m the fastest on average, and I’ve got the swagger to prove it.”

How It Works¶

Quick Sort also uses divide-and-conquer, but with a completely different strategy than Merge Sort:
1. Choose a pivot element from the array
2. Partition the array so everything less than the pivot goes left, everything greater goes right
3. Recursively sort the left and right partitions

The genius: after partitioning, the pivot is already in its final sorted position. No merge step needed.

Step-by-Step on [6, 3, 8, 1, 5, 2, 7, 4] (using last element as pivot)¶

[6, 3, 8, 1, 5, 2, 7, 4]   pivot = 4

Partitioning (elements <= 4 go left, > 4 go right):
  3 <= 4 -> left
  1 <= 4 -> left
  2 <= 4 -> left
  6 > 4  -> right
  8 > 4  -> right
  5 > 4  -> right
  7 > 4  -> right

Result: [3, 1, 2, |4|, 6, 8, 5, 7]
                    ^pivot in final position

Recursively sort left [3, 1, 2] and right [6, 8, 5, 7]:

Left [3, 1, 2], pivot = 2:
  [1, |2|, 3]

Right [6, 8, 5, 7], pivot = 7:
  [6, 5, |7|, 8]
  Left [6, 5], pivot = 5: [|5|, 6]

Final: [1, 2, 3, 4, 5, 6, 7, 8]

The Pivot Problem¶

The choice of pivot dramatically affects performance. This is Quick Sort’s Achilles’ heel:

Python Implementation¶

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    # Median-of-three pivot selection
    mid = len(arr) // 2
    pivot_candidates = [(arr[0], 0), (arr[mid], mid), (arr[-1], len(arr)-1)]
    pivot_candidates.sort(key=lambda x: x[0])
    pivot = pivot_candidates[1][0]

    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)
# In-place version (Lomuto partition scheme)
def quick_sort_inplace(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1

    if low < high:
        pivot_idx = partition(arr, low, high)
        quick_sort_inplace(arr, low, pivot_idx - 1)
        quick_sort_inplace(arr, pivot_idx + 1, high)
    return arr
def partition(arr, low, high):
    pivot = arr[high]  # Last element as pivot
    i = low - 1        # Index of the smaller element boundary

    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
# Test
data = [6, 3, 8, 1, 5, 2, 7, 4]
print(quick_sort(data))  # [1, 2, 3, 4, 5, 6, 7, 8]

data2 = [6, 3, 8, 1, 5, 2, 7, 4]
print(quick_sort_inplace(data2))  # [1, 2, 3, 4, 5, 6, 7, 8]

Complexity¶

• Best case: O(n log n), pivot always splits evenly
• Average case: O(n log n), very likely with randomized pivot
• Worst case: O(n^2), pivot is always the extreme value (mitigated by good pivot selection)
• Space: O(log n) for the recursion stack (in-place version), O(n) for the simple version
• Stable: No (in-place version); Yes (the simple list-comprehension version above)

The Verdict¶

Quick Sort is the default choice for general-purpose sorting in many real-world implementations. Despite the O(n^2) worst case, its average-case performance is excellent, and good pivot strategies make the worst case virtually impossible. It sorts in-place (saving memory) and has great cache performance.

The standard library sort in C++ (std::sort) starts with Quick Sort. It is the popular kid of sorting algorithms, and for good reason.

Contestant #6: Heap Sort: The Silent Professional¶

“O(n log n) guaranteed. O(1) space. No questions asked.”

How It Works¶

Heap Sort leverages the binary heap data structure:
1. Build a max-heap from the input array (a complete binary tree where each parent is greater than its children)
2. Repeatedly extract the maximum (the root) and place it at the end of the array
3. Heapify the reduced heap to maintain the heap property

Think of it as repeatedly asking “who is the tallest?” in a shrinking crowd and sending them to the back of the line.

The Heap as an Array¶

A binary heap can be stored as a flat array where for element at index i:
- Parent: (i - 1) // 2
- Left child: 2 * i + 1
- Right child: 2 * i + 2

No pointers, no node objects, just array math. Elegant.

Step-by-Step on [4, 10, 3, 5, 1]¶

Build max-heap:

Array: [4, 10, 3, 5, 1]

As a tree:        4
                /   \
              10     3
             / \
            5   1

Heapify from bottom-up:
  Heapify node 10 (index 1): children 5, 1 -> 10 > 5, 10 > 1 -> OK
  Heapify node 4 (index 0):  children 10, 3 -> 10 > 4 -> swap 4 and 10

After heapify:   10
                /   \
               5     3
              / \
             4   1

Array: [10, 5, 3, 4, 1]  <- Valid max-heap!

Extract and sort:

Step 1: Swap root (10) with last element (1)
  [1, 5, 3, 4, | 10]
  Heapify [1, 5, 3, 4] -> [5, 4, 3, 1]

Step 2: Swap root (5) with last unsorted (1)
  [1, 4, 3, | 5, 10]
  Heapify [1, 4, 3] -> [4, 1, 3]

Step 3: Swap root (4) with last unsorted (3)
  [3, 1, | 4, 5, 10]
  Heapify [3, 1] -> [3, 1]

Step 4: Swap root (3) with last unsorted (1)
  [1, | 3, 4, 5, 10]

Result: [1, 3, 4, 5, 10]

Python Implementation¶

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

    # Build max-heap (start from last non-leaf node)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Extract elements one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # Swap max to end
        heapify(arr, i, 0)                # Heapify reduced heap

    return arr
def heapify(arr, heap_size, root):
    """Ensure the subtree rooted at 'root' satisfies the max-heap property."""
    largest = root
    left = 2 * root + 1
    right = 2 * root + 2

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

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

    if largest != root:
        arr[root], arr[largest] = arr[largest], arr[root]
        heapify(arr, heap_size, largest)  # Recursively fix affected subtree
# Test
data = [4, 10, 3, 5, 1]
print(heap_sort(data))  # [1, 3, 4, 5, 10]

Complexity¶

• Best case: O(n log n)
• Average case: O(n log n)
• Worst case: O(n log n), guaranteed, like Merge Sort
• Space: O(1), in-place (unlike Merge Sort!)
• Stable: No

The Verdict¶

Heap Sort is the algorithm that does everything pretty well but nothing amazingly. It gives you guaranteed O(n log n) with O(1) extra space, a combination that no other algorithm in this list can match. Merge Sort is O(n log n) but needs O(n) space. Quick Sort is faster on average but can degrade to O(n^2).

Use Heap Sort when:
- You need guaranteed O(n log n) with O(1) space
- For implementing priority queues (the heap data structure itself is the star)
- As a fallback in hybrid algorithms, C++ std::sort (IntroSort) falls back to Heap Sort if Quick Sort degrades

Contestant #7: Counting Sort: The Rule-Breaker¶

“Comparison-based sorting has an O(n log n) lower bound? That’s cute. I don’t compare.”

How It Works¶

Counting Sort is fundamentally different from every other algorithm in this list. Instead of comparing elements, it counts the occurrences of each value and uses arithmetic to determine the correct position. This breaks the O(n log n) barrier entirely, but it only works when the range of input values (k) is known and reasonably small.

Step-by-Step on [4, 2, 2, 8, 3, 3, 1]¶

Input: [4, 2, 2, 8, 3, 3, 1]
Range: 0 to 8 (k = 9)

Step 1: Count occurrences
  Value:  0  1  2  3  4  5  6  7  8
  Count: [0, 1, 2, 2, 1, 0, 0, 0, 1]

Step 2: Cumulative count (prefix sum)
  Count: [0, 1, 3, 5, 6, 6, 6, 6, 7]
  This tells us: values <= 1 occupy positions 0-0,
                 values <= 2 occupy positions 1-2, etc.

Step 3: Place elements (iterate input right-to-left for stability)
  Process 1: count[1] = 1 -> place at index 0, count[1] = 0
  Process 3: count[3] = 5 -> place at index 4, count[3] = 4
  Process 3: count[3] = 4 -> place at index 3, count[3] = 3
  Process 8: count[8] = 7 -> place at index 6, count[8] = 6
  Process 2: count[2] = 3 -> place at index 2, count[2] = 2
  Process 2: count[2] = 2 -> place at index 1, count[2] = 1
  Process 4: count[4] = 6 -> place at index 5, count[4] = 5

Output: [1, 2, 2, 3, 3, 4, 8]

Python Implementation¶

def counting_sort(arr):
    if not arr:
        return arr

    # Find the range
    max_val = max(arr)
    min_val = min(arr)
    range_size = max_val - min_val + 1

    # Create count array and output array
    count = [0] * range_size
    output = [0] * len(arr)

    # Step 1: Count occurrences (shift values by min_val to handle negatives)
    for num in arr:
        count[num - min_val] += 1

    # Step 2: Cumulative count
    for i in range(1, range_size):
        count[i] += count[i - 1]

    # Step 3: Place elements (right-to-left for stability)
    for i in range(len(arr) - 1, -1, -1):
        idx = count[arr[i] - min_val] - 1
        output[idx] = arr[i]
        count[arr[i] - min_val] -= 1

    return output
# Test
data = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(data))  # [1, 2, 2, 3, 3, 4, 8]

# Works with negative numbers too
data2 = [3, -1, 0, -5, 2, -3, 1]
print(counting_sort(data2))  # [-5, -3, -1, 0, 1, 2, 3]

Complexity¶

• Best case: O(n + k)
• Average case: O(n + k)
• Worst case: O(n + k), where k is the range of input values
• Space: O(n + k), needs count array and output array
• Stable: Yes

The Verdict¶

Counting Sort is a specialist. When conditions are right (integers with a small range) it absolutely destroys every comparison-based algorithm. O(n + k) is linear when k is proportional to n. Use it for:

• Sorting exam scores (0-100)
• Sorting ASCII characters (0-127)
• Sorting ages (0-150)
• Sorting pixel values (0-255)
• As a subroutine in Radix Sort for sorting larger numbers digit by digit

Warning: If the range is huge (e.g., sorting 100 numbers in range 0 to 1,000,000,000), Counting Sort creates a billion-element count array. That is 4 GB of memory just for the count array. Comparison-based sorts would finish instantly. Know your data before reaching for this one.

The Grand Comparison Table¶

Here it is, all seven contestants, side by side:

Quick Sort can be made stable at the cost of O(n) space.

Which Algorithm for Which Situation?¶

This is the part that actually matters in practice. Here is your decision guide:

What Real Programming Languages Actually Use¶

Here is a fun fact: no production language uses a single sorting algorithm. They all use hybrid algorithms that combine the strengths of multiple approaches:

Key insight: No single algorithm wins in all cases. Real-world sorts are hybrid approaches that pick the right strategy based on the input characteristics. TimSort is particularly clever, it takes advantage of naturally occurring “runs” in real data, which is extremely common (logs are timestamped, database results have partial order, etc.).

The Final Score¶

Understanding sorting algorithms is not about memorizing implementations (that is what documentation is for). It is about understanding the trade-offs each one makes:

• Time vs. Space: Merge Sort is fast and stable but needs O(n) extra memory. Heap Sort is fast and in-place but is not stable.
• Average vs. Worst Case: Quick Sort is the fastest on average but can degrade to O(n^2). Merge Sort is slightly slower on average but guarantees O(n log n).
• Simplicity vs. Performance: Insertion Sort is trivially simple and excellent for small inputs. For large inputs, you need more sophisticated algorithms.
• Comparison vs. Non-Comparison: When the data has special properties (bounded integers), non-comparison sorts like Counting Sort can achieve linear time.

The best engineers don’t just know these algorithms, they know when to use each one. They understand the principles behind them: divide-and-conquer, heap properties, the power of reducing the problem space, and the fundamental O(n log n) barrier for comparison-based sorts.

And when in doubt? Just call .sort() and let TimSort handle it. The language designers already made the optimal choice for you.

Why do sorting algorithms never win talent shows? Because no matter how good they are, they always get compared!