Sorting Algorithms (Bubble, Insertion, Quick Sort)

1. Overview

A. Definition

A sorting algorithm is a technique that rearranges a given set of data into order according to a user-specified criterion (ascending/descending); it is the most fundamental algorithm and governs the efficiency of other operations such as search, merge, and aggregation.

Sorting is one of the most studied problems in computer science and lies at the very bottom of virtually every application system. Building database indexes, pre-sorting for binary search, deduplication, and computing medians and quantiles in statistical processing all presuppose sorting. Why is sorting important? Because in sorted data, binary search enables O(log n) lookups and adjacent duplicates can be removed in O(n), so the complexity of downstream operations drops dramatically. Conversely, if sorting is slow, everything built on top of it slows down with it.

B. Three axes for understanding sorting: time, stability, memory

The key to understanding sorting algorithms is the 'trade-off among time complexity, stability, and extra memory'. Simple algorithms (bubble, insertion, selection) are easy to understand and implement but slow down sharply to O(n²) as data grows, while divide-and-conquer-based ones (quick, merge) are far faster at an average of O(n log n) but are complex to implement or require extra memory. Added to this are 'does it preserve the relative order of equal values (stability)' and 'how much extra memory does it use (whether it is in-place)', which change the appropriate choice for a given situation.

This trade-off is not abstract theory but directly governs practical choices. For example, if the data is nearly sorted, simple insertion sort is actually faster than quicksort; for large random data, quicksort is advantageous; and in an embedded environment with extremely constrained memory, an in-place sort that uses no extra memory is mandatory. In other words, there is no absolute answer for the "fastest sort"; the optimum changes with the data's size, initial state, memory constraints, and stability requirements.

C. Stability and in-place sorting

A stable sort preserves the original order of elements with equal values, which is decisively important in multi-criteria sorting (first by name, then by age). When sorting first by name and then again by age, the age sort must be stable so that the name order is preserved within the same age. An in-place sort uses almost no extra memory (O(1)–O(log n)) beyond the input array, which is advantageous in memory-constrained environments. These two properties are mutually independent, so there exist both sorts that are stable but use extra memory (merge) and sorts that are in-place but unstable (quick).

2. Classification of Sorting Algorithms

Sorting algorithms fall broadly into comparison-based and non-comparison categories. Comparison-based sorts determine order by comparing elements with one another, and it is proven that the lower bound on the number of comparisons is theoretically O(n log n). Non-comparison-based sorts (counting, radix, bucket) directly exploit the distribution of values or the number of digits to reach O(n) under certain conditions, but they have constraints on the data range. The classification diagram below shows the position of the three algorithms covered in this topic.

flowchart TB
  ROOT["Sorting algorithms"] --> CMP["Comparison-based (lower bound O(n log n))"]
  ROOT --> NCMP["Non-comparison (counting/radix/bucket)"]
  CMP --> SIMPLE["Simple O(n squared)"]
  CMP --> ADV["Advanced O(n log n)"]
  SIMPLE --> BUB["Bubble sort"]
  SIMPLE --> INS["Insertion sort"]
  SIMPLE --> SEL["Selection sort"]
  ADV --> QUICK["Quicksort (divide and conquer)"]
  ADV --> MERGE["Merge sort (divide and conquer)"]
  ADV --> HEAP["Heap sort"]

In this classification, bubble and insertion sort belong to the simple O(n²) family, and quicksort belongs to the advanced O(n log n) family of divide-and-conquer. The simple family has great educational value in intuitively showing "why sorting is hard," while the advanced family is what is actually used in practice. Looking at the three algorithms side by side is the best way to understand where the gap between O(n²) and O(n log n) comes from.

3. Bubble Sort

A method that repeatedly compares two adjacent elements and swaps them if they are in the wrong order, so that large values float to the back of the array like bubbles.

Bubble sort scans the array once from beginning to end, comparing and swapping adjacent elements. When one pass finishes, the largest value is fixed at the very back. The next pass scans again excluding the fixed last element to fix the second-largest value, and repeating this n-1 times sorts the whole array. The name comes from the image of large values floating to the back like bubbles on water.

Bubble sort's biggest feature is that it is the simplest to implement. It is completed with a double loop and one swap line, so it is widely used in introductory algorithm education. However, because it repeats adjacent comparison and swapping every pass, its actual performance is the worst. For n elements, about n²/2 comparisons and swaps occur, so it slows down sharply even with a small increase in data.

One optimization is the flag technique that stops if no swap occurs at all in a pass, since the array is already sorted. Applying this optimization allows termination in O(n) for already-sorted input. But for random data it is still O(n²), so even with this optimization, bubble sort remains educational rather than practical.

• Complexity: time average/worst O(n²), best O(n) (with optimization), space O(1), stable sort
• Use: educational / very small data. Unsuitable for practical large-scale sorting.

4. Insertion Sort

A method that takes new elements one at a time and inserts each into its correct place in a sorted subarray, just like sorting the cards in one's hand.

Insertion sort starts from the second element and inserts it into the right place by comparing it with the already-sorted section in front. While finding the insertion position, elements larger than it are pushed back one slot. It is exactly like the motion of slotting a newly received card between the sorted cards in one's hand, so it is intuitively easy to understand.

Insertion sort's decisive strength is that it is sensitive to the initial state of the input. The worst case (reverse order) is O(n²), but for already-nearly-sorted data, almost no comparisons occur, so it approaches O(n) and is very fast. This is because if each element is close to its right place, there are almost no elements to push back. Thanks to this adaptive property, for small-scale or partially sorted data it can be even more practical than quicksort.

Precisely because of this property, insertion sort is used in practice as an auxiliary tool for other sorts. As quicksort or merge sort recursively splits the array into smaller pieces, when a subarray's size becomes small enough (usually 10–32) or less, it switches to insertion sort instead of divide-and-conquer, which has large recursion overhead. In small arrays, insertion sort's small constant factor actually makes it faster.

• Complexity: time average/worst O(n²), best O(n), space O(1), stable sort
• Use: small-scale/partially sorted data, the finishing stage of hybrid sorts.

5. Quick Sort

A divide-and-conquer algorithm that picks one pivot, partitions the array into values smaller and larger than it, and recursively sorts each part again.

Quicksort performs a partition that divides the array into two groups (values smaller than the pivot, values larger) based on the pivot. When partitioning finishes, the pivot fixes its final sorted position, and recursively sorting the left and right subarrays the same way sorts the whole array. The diagram below shows how divide-and-conquer recursively splits and recombines the array.

flowchart TB
  A["Array: 5 3 8 1 9 2 (pivot=5)"] --> L["Smaller: 3 1 2"]
  A --> P["Pivot fixed: 5"]
  A --> R["Larger: 8 9"]
  L --> L1["pivot=3 -> 1 2 | 3"]
  R --> R1["pivot=8 -> 8 | 9"]
  L1 --> RES["Merged result: 1 2 3 5 8 9"]
  R1 --> RES

Quicksort is widely used as the fastest sort on average. This is because it is close to an in-place sort (using only the recursion stack) and has good cache locality, giving it a small constant factor. However, it has a fatal weakness. If the pivot is chosen poorly, the partition skews to one side and it degrades to worst-case O(n²). For example, always picking the first element as the pivot on already-sorted data separates only one element each time, requiring n partitions.

To avoid this worst case, practice refines the pivot-selection strategy. Representative examples are median-of-three, which uses the median of the values at three points (start, middle, end) as the pivot, and randomized quicksort, which picks the pivot at random. Randomization prevents a specific input from always causing the worst case, so an average of O(n log n) can be expected for any input. The Introsort technique is also used, which switches to heap sort when recursion depth grows too deep, guaranteeing worst-case O(n log n).

• Complexity: time average O(n log n), worst O(n²), space O(log n) (recursion stack), unstable sort
• Use: general-purpose high-speed sorting of large random data (C++ STL, etc.).

6. Comparison and Cases

The difference among the three algorithms ultimately comes down to "how wastelessly comparisons and swaps are done." Bubble and insertion handle only adjacent elements, so a single comparison cannot send an element far, keeping them at O(n²); quicksort splits elements into half-sized groups in one stroke via pivot partitioning, achieving O(n log n). The table and graph below summarize this difference.

Algorithm	Average	Worst	Best	Space	Stability	Key feature
Bubble sort	O(n²)	O(n²)	O(n)	O(1)	Stable	Adjacent swap, educational
Insertion sort	O(n²)	O(n²)	O(n)	O(1)	Stable	Strong on partial sort, adaptive
Quicksort	O(n log n)	O(n²)	O(n log n)	O(log n)	Unstable	Divide-and-conquer, fastest on average

{
  "type": "bar",
  "data": {
    "labels": ["Bubble", "Insertion", "Quick"],
    "datasets": [{
      "label": "Average comparison operations (n=1000, relative)",
      "data": [1000000, 250000, 10000],
      "backgroundColor": ["#e11d48", "#f59e0b", "#2f6fed"]
    }]
  },
  "options": {
    "plugins": { "legend": { "display": false }, "title": { "display": true, "text": "Average operation-count comparison (conceptual example)" } },
    "scales": { "y": { "title": { "display": true, "text": "Operation count (relative)" } } }
  }
}

The graph above shows how dramatic the difference in operation counts is between the O(n²) family (bubble, insertion) and the O(n log n) family (quick) at n=1000. At n=1000, O(n²) is about one million and O(n log n) is about ten thousand—a hundredfold difference—and as data grows this gap widens exponentially. At n=1,000,000, O(n²) is about 10¹² operations and O(n log n) about 2×10⁷; at one billion operations per second, that is roughly 1,000 seconds versus 0.02 seconds—the very line between being practical or not.

As a concrete case, when a database processes an ORDER BY clause, it uses a quicksort/Introsort family if it can fit in memory, and disk-based external merge sort if it exceeds memory. Conversely, when maintaining and inserting into a nearly-sorted stream in real time (e.g., log timestamps), the insertion-sort family is advantageous as it approaches O(n).

7. Deep Dive: Hybrid Sorting in Practical Libraries

The most important insight in practice is that "a single algorithm is not used as-is." Standard libraries adopt hybrid sorts that combine the strengths of several algorithms.

Java (object sorting in Arrays.sort) and Python (sorted, list.sort) use Timsort. Timsort combines merge sort and insertion sort; if there are already-sorted sections (runs) in the data, it detects and merges them, so it approaches O(n) on real-world data (which is often partially sorted). That it is a stable sort is also important for multi-criteria sorting.

C++ STL's std::sort uses Introsort. It starts with quicksort by default but switches to heap sort if the recursion depth exceeds 2·log n (a signal of heading toward the worst case), guaranteeing O(n log n) even in the worst case, and finishes with insertion sort when subarrays get small. In other words, it takes quicksort's average speed, heap sort's worst-case guarantee, and insertion sort's small-scale efficiency all at once.

This hybrid design shows how the trade-offs seen above are synthesized in the field. Since no single algorithm can be optimal in every situation, it dynamically switches algorithms according to the data's size and initial state, securing "average performance, worst-case guarantee, and stability" together. From a professional engineer's perspective, when discussing sorting one must be able to go beyond memorizing the complexity of individual algorithms to the design judgment of combining and selecting algorithms according to requirements.

8. Considerations and Implications

1. There is no absolute optimum (situational fit): The optimal sort changes with the data's size, initial state, memory constraints, and stability requirements. Nearly-sorted small data suits insertion, large random data suits quick, and when stability is needed merge/Timsort is appropriate.
2. Avoiding quicksort's worst-case O(n²) (robustness): One should pick the pivot at random or by median-of-three and switch to heap sort when recursion depth is exceeded (Introsort) to defend against the worst case. If the sort target is external input, even the possibility of maliciously induced worst cases (algorithmic-complexity attacks) should be considered.
3. Identifying stability requirements (correctness): For work that requires multi-criteria sorting or order preservation, one must choose a stable sort (merge/Timsort) instead of the unstable quicksort so that results come out as intended.
4. Choice in memory-constrained environments (resource efficiency): In embedded/large-scale environments, the amount of extra memory used is the crux. One distinguishes between in-place sorts (quick, heap) and external sorts (disk-based merge) by whether the data fits in memory.
5. Trusting and verifying libraries (practical principle): Unless there is a special reason, using a proven standard library (Timsort, Introsort) is safe. A hand-rolled implementation is prone to bugs in boundary, duplicate, and worst cases, so one should consider an optimized implementation only when performance requirements are clear.

References

• Cormen et al., "Introduction to Algorithms", MIT Press (divide-and-conquer, sorting lower bound)
• CPython Timsort listsort description: https://github.com/python/cpython/blob/main/Objects/listsort.txt
• cppreference std::sort (Introsort): https://en.cppreference.com/w/cpp/algorithm/sort

---

In one line: Bubble and insertion sort are simple O(n²) sorts (insertion is adaptively efficient on nearly-sorted data), and quicksort is a divide-and-conquer at average O(n log n) that is fast but worst-case O(n²) depending on the pivot; the crux is the design judgment of choosing merge sort or a hybrid (Timsort, Introsort) according to stability, data characteristics, and memory constraints.