Skip to content
Tutorials Center
My learning

Topics

Lesson 88 of 135 · Data Structures in C

Sorting and Searching Algorithms

Implement bubble, selection, insertion, merge and quick sort in C, count their work, write a correct binary search, and time every algorithm with clock().

The standard library already sorts for you: qsort handles any array with a comparison function, and in real programs you should use it. So why write sorting algorithms yourself? Because they are the clearest possible introduction to algorithm analysis. Five short functions that all produce the same result show, in a way no theory can, why some approaches take a millisecond and others take minutes on the same data. They also teach the array-index discipline that C demands, and they come up in every programming interview.

In this lesson you'll implement the three simple sorts (bubble, selection, insertion), the two fast divide-and-conquer sorts (merge sort and quicksort), and binary search, with counters that show how much work each does. At the end, you'll race them against each other and against qsort with clock() from <time.h>.

How sorts are compared

Three properties describe a sorting algorithm:

  • Time complexity. How the work grows with the number of elements n. O(n²) means doubling n makes the work four times bigger; O(n log n) means doubling n makes it only a little more than twice as big. For a million elements, n² is 10¹² while n log₂ n is about 2 × 10⁷: the difference between hours and a blink.
  • Extra memory. An in-place sort needs only O(1) extra space (a few variables). Merge sort needs a buffer as big as the input.
  • Stability. A stable sort keeps equal elements in their original relative order. That matters when sorting records by one key after another, for example sorting people by city after sorting them by name.

Best, average and worst cases can differ. Insertion sort is O(n) on input that's already sorted but O(n²) on reversed input; quicksort is O(n log n) on average but O(n²) when its pivots are chosen badly.

The simple O(n²) sorts

All three simple sorts divide the array into a sorted part and an unsorted part and grow the sorted part one element at a time:

  • Bubble sort repeatedly walks the array and swaps neighbors that are out of order. After each pass, the largest remaining element has "bubbled" to the end. If a pass makes no swaps, the array is sorted and you can stop early.
  • Selection sort finds the smallest element of the unsorted part and swaps it to the front of that part. It always makes exactly n(n−1)/2 comparisons, but at most n−1 swaps, which helps when writes are expensive.
  • Insertion sort takes the next element and shifts it left into its place among the already sorted elements, like sorting a hand of cards. It's fast on small or nearly sorted arrays, which is why real-world sorts use it for small pieces.

The example runs all three on the same data and counts comparisons and element moves:

C Bubble, selection and insertion sort

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

All three produce 3 3 10 15 29 41 56 64 72 88, but the counts differ. Selection sort always makes 45 comparisons for 10 elements (9 + 8 + ... + 1). Insertion sort makes the fewest moves, because shifting an element costs one write where a swap costs three. Try sorting an array that's already in order: bubble and insertion sort drop to 9 comparisons, while selection sort still makes 45.

Pay attention to size_t loops that count down. for (size_t j = i; j >= 0; j--) would never stop, because an unsigned value is always ≥ 0 and 0 - 1 wraps to a huge number. The code above tests j > 0 and reads a[j - 1] instead (see Type Conversions and Casts).

Merge sort

Merge sort is the classic divide-and-conquer algorithm:

  1. Split the array into two halves.
  2. Sort each half recursively (Recursion).
  3. Merge the two sorted halves into one sorted run by repeatedly taking the smaller of the two front elements.

Each level of recursion does O(n) merging work, and halving gives about log₂ n levels, so merge sort is O(n log n) in every case, best, average and worst. It's also stable if the merge takes from the left half when elements are equal (<=). The price is an O(n) temporary buffer, allocated once here and reused by every merge:

C Merge sort with one shared buffer

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Sixteen elements need a recursion depth of 5 (16 → 8 → 4 → 2 → 1), which is 1 + log₂ 16. A million elements would need only 21 levels, so the recursion is never a stack risk. The range is half-open, [lo, hi): lo is included and hi is not. Half-open ranges make sizes simply hi - lo, splits clean ([lo, mid) and [mid, hi)), and empty ranges natural, which removes a whole class of off-by-one errors.

Merge sort is the algorithm of choice for linked lists (merging needs no random access and no buffer there) and for data too big for memory (external sorting), and it's the core of stable sorts in many languages' standard libraries.

Quicksort

Quicksort also divides and conquers, but does its work before recursing:

  1. Pick a pivot element.
  2. Partition: rearrange the array so everything smaller than the pivot comes before it and everything larger comes after. The pivot is now in its final position.
  3. Recursively sort the two sides.

There's no merge step and no buffer, so quicksort is in-place and usually the fastest comparison sort in practice. The danger is the pivot. If it's always the smallest or largest element (for example, picking the first element of already sorted data), each partition peels off just one element, the recursion gets n levels deep, and the time becomes O(n²). Choosing the median of three (first, middle, last) avoids that for sorted and reversed input. Recursing into the smaller side and looping on the larger one guarantees the stack depth stays O(log n) no matter what.

C Quicksort with median-of-three pivots

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

For n = 1,000, n log₂ n is about 10,000, and all three large runs land in that neighborhood (roughly 8,000 to 14,000) instead of the 500,000 comparisons a naive first-element pivot would need on sorted input. The small run shows duplicates are handled correctly.

Look carefully at the index arithmetic, because this is where quicksort implementations break. With size_t indexes, p - 1 when p is 0 wraps around to a huge value, so the code checks p > lo before recursing and p == lo before shrinking hi. Quicksort is not stable: partitioning swaps elements over long distances.

Note: Despite its name, C's qsort isn't required to be quicksort. glibc's implementation has historically used merge sort when memory allows; others use introsort (quicksort that switches to heapsort if recursion gets too deep, plus insertion sort for tiny ranges). The standard promises only that it sorts, so never rely on qsort being stable.

Once data is sorted, finding a value no longer means checking every element. Binary search compares the target with the middle element and discards the half that can't contain it. Each step halves the range, so it needs at most about log₂ n + 1 comparisons: 20 for a million elements, versus up to a million for a linear scan.

Binary search is famous for being easy to explain and hard to get right. Two classic bugs:

  • Overflow in the midpoint. (lo + hi) / 2 can overflow when indexes are large. lo + (hi - lo) / 2 can't.
  • Off-by-one loops that never end or skip the last element. Using a half-open range [lo, hi) with while (lo < hi) and hi = mid (not mid - 1) avoids both.

The most useful variant is lower bound: return the first index whose element is not less than the target. It finds the target if present, the first of several duplicates, and otherwise the position where the target would be inserted to keep the array sorted.

C Binary search and lower bound

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

4 appears three times, and lower bound reports the first one, index 1. 99 would go at the very end (index 12, which is n), and -5 at the very beginning. No search takes more than 4 steps for 12 elements, since ⌈log₂ 13⌉ is 4. Change the Input box to try your own values.

The race: timing with clock()

Counting comparisons shows the shape of the cost; timing shows the real thing. clock() returns the processor time used by the program, in units of CLOCKS_PER_SEC. Subtract two readings and divide to get seconds. This program sorts the same 20,000 pseudo-random numbers with each algorithm and checks every result:

C Timing four sorts and qsort

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Your exact numbers will differ from run to run and machine to machine, but the pattern is dramatic: the two O(n²) sorts take tens or even hundreds of milliseconds (selection sort is usually the slowest, because its inner loop always scans to the end), while merge sort, quicksort and qsort finish in a couple of milliseconds. Change N to 40000 and the quadratic sorts take about four times as long, while the fast ones barely double. That is O(n²) versus O(n log n) in action. (qsort is often a bit slower than the hand-written quicksort because it calls the comparison function through a pointer for every comparison; it's still the right default, being tested and generic.)

Tip: For trustworthy timings, repeat each measurement several times and take the minimum, sort the same input for every algorithm (as above, with memcpy from one original), and make the program use the result so the optimizer can't delete the work. Here the sortedness check does that.

Complexity at a glance

Algorithm Best Average Worst Extra memory Stable
Bubble sort (early exit) O(n) O(n²) O(n²) O(1) Yes
Selection sort O(n²) O(n²) O(n²) O(1) No
Insertion sort O(n) O(n²) O(n²) O(1) Yes
Merge sort O(n log n) O(n log n) O(n log n) O(n) Yes
Quicksort O(n log n) O(n log n) O(n²) O(log n) stack No
Linear search O(1) O(n) O(n) O(1) n/a
Binary search (sorted input) O(1) O(log n) O(log n) O(1) n/a

In practice: use qsort and bsearch for arrays (qsort and bsearch), insertion sort for tiny or nearly sorted arrays, merge sort for linked lists and when you need stability, and a hash table instead of sorting when you only need exact lookups.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. An O(n²) sort takes 1 second for 10,000 elements. Roughly how long does it take for 20,000?

    Doubling n multiplies n² by four. An O(n log n) sort would take only a little more than twice as long.
  2. 2. Which simple sort makes the same number of comparisons whether the input is sorted, reversed or random?

    Selection sort always scans the entire unsorted part to find the minimum, so it makes n(n−1)/2 comparisons every time.
  3. 3. Why does the merge step use a[i] <= a[j] rather than a[i] < a[j]?

    With <, equal elements from the right half would be placed first, reversing their original order.
  4. 4. What happens with this loop? for (size_t j = n - 1; j >= 0; j--)

    When j is 0, j-- wraps around to SIZE_MAX, so the condition stays true and the loop reads far outside the array.
  5. 5. Using lower_bound on {1, 3, 3, 3, 9}, what index does a search for 3 return, and what does a search for 5 return?

    Lower bound returns the first element that is not less than the target. The first 3 is at index 1; the first element not less than 5 is 9, at index 4.

Summary

  • Sorting algorithms are compared by time complexity, extra memory and stability; O(n log n) beats O(n²) enormously as n grows.
  • Bubble, selection and insertion sort are O(n²); insertion sort is the best of them and is fast on small or nearly sorted data.
  • Merge sort is O(n log n) in every case and stable, but needs an O(n) buffer; it's ideal for linked lists.
  • Quicksort partitions around a pivot and is usually fastest in practice; median-of-three pivots and recursing on the smaller side prevent the worst cases.
  • Binary search needs sorted data and finds values in O(log n); use half-open ranges and lo + (hi - lo) / 2, and prefer the lower-bound form.
  • Watch unsigned index arithmetic in downward loops and p - 1 expressions.
  • Time code with clock() and CLOCKS_PER_SEC; in real programs, reach for qsort and bsearch first.

Next: Multi-File Programs and Linkage, where you'll split a program into headers and source files the way real C projects are organized.