Summary
Table 10.2 summarizes the characteristics of the sorting methods discussed in this chapter.
| Sorting Method | Average | Worst Case | Stable | In Place | Remark |
|---|---|---|---|---|---|
| Insertion | O(n^2) | O(n^2) | Yes | Yes | Good for few items and teaching purposes |
| Bubble | O(n^2) | O(n^2) | Yes | Yes | Good for teaching purposes and easily maintainable code |
| Shell | O(n^1.25) | O(n^1.5) | No | Yes | Good for general purpose and time-critical systems |
| Heap sort | O(nlog2 n) | O(nlog2 n) | No | Yes | Best for time-critical systems and large lists |
| Quick sort | O(nlog2 n) | O(n^2) | No | No | Best for many strings |
| Radix sort | O(m*n) | O(m*n) | No | No | Perfect for large lists with numbers |
Note that often interesting results can be gained by combining sorting algorithms. Think, for instance, ...
Get C++ Footprint and Performance Optimization now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
