Bubble, Insertion and Quick Sort in C, Measured

Revised November 2026. This tutorial first appeared in Korean in 2021. We recompiled and re-ran all three examples with Apple clang 21 on an Apple M1 Pro. The bubble sort example printed something different from the article (no spaces between numbers). The quicksort was correct on 200,000 random arrays but crashed with a stack overflow on 300,000 already-sorted numbers. Below are the causes, the fixed code and measured timings.

What sorting is

Sorting rearranges data into order by some key: lining students up by height, shelving books by title. Sorted data enables fast lookups such as binary search.

Bubble sort

Bubble sort compares neighbouring elements and swaps them when they are out of order. Large values "bubble up" to the end.

Bubble sort

In the figure, 84 and 69 are compared and swapped, then 84 and 76, and then 84 stays put because 86 is larger. Each pass fixes the largest remaining value at the end, so every pass compares one element fewer.

Comparisons = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2

The 2021 article called 49,995,000 the number of swaps for 10,000 items. It is the number of comparisons. We counted (n = 10,000):

The original text said the loop "exits when no more swaps happen", but the example code had no early exit. With one (last row), sorted input finishes after 9,999 comparisons. The complexity is O(n²), with a best case of O(n) when the early exit is present.

void BubbleSort(int DataArray[], int Length)
{
    for (int i = 0; i < Length - 1; i++)
    {
        int swapped = 0;                              /* 2026: early exit */
        for (int j = 0; j < Length - (i + 1); j++)
        {
            if (DataArray[j] > DataArray[j + 1]) {
                int temp = DataArray[j + 1];
                DataArray[j + 1] = DataArray[j];
                DataArray[j] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break;                          /* no swaps: already sorted */
    }
}

The output bug in the 2021 example

The original printed with printf("%d", DataArray[i]), with no separator. The article showed 2 3 4 5 7, but the program actually printed:

$ printf "5\n7 5 4 3 2\n" | ./bubble
...: 23457

printf("%d ", DataArray[i]) fixes it. The array allocated with malloc should also be released with free(DataArray);.

Insertion sort

Insertion sort takes the next unsorted element and inserts it into the right place in the already-sorted front part, the way you sort cards in your hand.

1. Compare 3 and 4: 4 is larger, no change.
2. Compare 4 and 6: no change.
3. Compare 6 and 2: take 2 out and insert it before 3.
4. Compare 6 and 8: no change.
5. Compare 8 and 1: take 1 out and insert it before 2.

Best case O(n) (already sorted); average and worst case O(n²). Average comparisons are about n(n-1)/4, fewer than bubble sort, and in the measurements below it was about five times faster.

void InsertionSort(int arrData[], int Length)
{
    for (int i = 1; i < Length; i++)
    {
        int key = arrData[i], j = i - 1;
        while (j >= 0 && arrData[j] > key) {          /* shift larger values right */
            arrData[j + 1] = arrData[j];
            j--;
        }
        arrData[j + 1] = key;                         /* insert into the gap */
    }
}

The 2021 example worked, but its print helper drew a compiler warning:

void PrintArray(int arrData[], int Length)
{
    for (int i = 0; i < Length; i++)
        printf("%d ", arrData[i]);
        printf("\n");          /* looks like part of the loop; it is not */
}

warning: misleading indentation; statement is not part of the previous 'for'

It behaves as intended (one newline at the end), but the indentation lies to the reader. Align it with the for, or use braces.

Quick sort

Quick sort is divide and conquer. Pick a pivot, move smaller values to the left and larger ones to the right, then repeat on both parts.

1. Pick 5 as the pivot; smaller values go left, larger go right.
2. In the left part, pick 4 and repeat.
3. In the right part, pick 8 and repeat.

Average complexity is O(n log n); worst case O(n²).

The 2021 implementation, using the first element as the pivot:

int Partition(int numbers[], int left, int right)
{
    int first = left;
    int pivot = numbers[first];          /* first element is the pivot */
    int temp = 0;
    ++left;
    while (left <= right)
    {
        while (numbers[left] <= pivot && left < right) ++left;
        while (numbers[right] > pivot && left <= right) --right;
        if (left < right) {
            temp = numbers[left]; numbers[left] = numbers[right]; numbers[right] = temp;
        }
        else break;
    }
    temp = numbers[first]; numbers[first] = numbers[right]; numbers[right] = temp;
    return right;
}

void QuickSort(int numbers[], int left, int right)
{
    if (left < right)
    {
        int index = Partition(numbers, left, right);
        QuickSort(numbers, left, index - 1);
        QuickSort(numbers, index + 1, right);
    }
}

Is it correct? 200,000 checks

We sorted 200,000 random arrays (length 0–50, narrow value ranges so there are many duplicates) and compared each against the C library's qsort: zero mismatches. The implementation is correct.

The problem is sorted input

With the first element as pivot, a sorted array makes the pivot the minimum every time. One side is empty and n-1 elements remain on the other, so the work is O(n²) and the recursion depth is n.

Recursion depth n can overflow the stack. We tested sorted arrays with an 8 MB stack limit:

The -O2 build survived because the compiler turned the last recursive call into a loop (tail-call optimisation). The same code crashes in a debug build and survives in a release build, which is one of the hardest kinds of bug to track down.

The fixed quicksort

Two changes: use the middle element as the pivot (swap it to the front and reuse the existing Partition), and recurse only into the smaller part, looping over the larger one. That caps recursion depth at log₂n.

void QuickSortFixed(int numbers[], int left, int right)
{
    while (left < right)
    {
        int mid = left + (right - left) / 2;               /* middle element as pivot */
        int t = numbers[left]; numbers[left] = numbers[mid]; numbers[mid] = t;
        int index = Partition(numbers, left, right);
        if (index - left < right - index) {                /* recurse into the smaller side */
            QuickSortFixed(numbers, left, index - 1);
            left = index + 1;
        } else {
            QuickSortFixed(numbers, index + 1, right);
            right = index - 1;
        }
    }
}

The fixed version also had zero mismatches over 200,000 random arrays. On bad inputs:

Speed of the three sorts (measured)

Random ints, clang -O2, Apple M1 Pro:

With 10× more data, insertion sort took about 96× longer (O(n²) predicts 100×) and quick sort about 13× (O(n log n)). Bubble sort grew about 330×, far above theory. We did not analyse why, and the 0.027 s baseline is small enough to be noisy. qsort is a little slower than the hand-written quicksort because it calls the comparison function through a pointer.

In real code

• Use the library: qsort in C, std::sort in C++, sorted()/list.sort() in Python, Array.Sort/List.Sort in C#. They already handle worst-case inputs and recursion depth (std::sort is typically an introsort).
• Write your own to learn. If you do, always test sorted, reversed and duplicate-heavy inputs, and run a debug (-O0) build too.
• Insertion sort is surprisingly fast on small, nearly sorted data, which is why many library sorts switch to it for small ranges.