Thinking
When dealing with small sequences, there are several reasons for preferring algorithms that can achieve O(n) time complexity:
- Adaptability: Algorithms like insertion sort can take advantage of the initial degree of order in the input data. If the data is already partially sorted (which is more likely in small datasets), these types of algorithms can perform closer to linear efficiency.
- Memory Access: Small datasets can be fully accommodated in the CPU cache, reducing the need to access main memory. This can significantly speed up O(n) algorithms, as they typically have good spatial locality, making full use of the cache.
- Overhead: More complex algorithms (such as quicksort or merge sort) usually have a larger setup overhead (e.g., recursive stack calls or additional memory allocations). In small datasets, this overhead might not be sufficiently amortized, making simple algorithms more advantageous in terms of performance.
Comparison Table of Sorting Algorithms
| Sorting Algorithm | Average Time Complexity | Best Case | Worst Case | Space Complexity | Sorting Method | Stability |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n^2) | O(n) | O(n^2) | O(1) | In-place | Stable |
| Insertion Sort | O(n^2) | O(n) | O(n^2) | O(1) | In-place | Stable |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Not in-place | Stable |
| Bucket Sort | O(n + k) | O(n) | O(n^2) | O(n + k) | Not in-place | Stable |
Round 1:
Contestants: Bubble Sort, Insertion Sort, Counting Sort, Bucket Sort
Non-in-place sorting requires additional memory allocation, which is time-consuming, therefore eliminating Counting Sort and Bucket Sort.
Round 2:
Contestants: Bubble Sort, Insertion Sort, Counting Sort，Bucket Sort
During the swap of adjacent elements in Bubble Sort, it involves three assignment operations（using a temporary variable for the swap）
In Insertion Sort, before finding the insertion point, it only requires moving the element backwards, which typically involves only one assignment operation.