Sorting Algorithms Explained: In-Place, Comparison-Based, and Time Complexity
| Algorithm | In-Place Sort | Comparison-Based | Average Performance | Time Complexity |
|---|---|---|---|---|
| Selection Sort | Y | Y | O(n²) | O(n²) |
| Bubble Sort | Y | Y | Depends on input state | O(n²) |
| Insertion Sort | Y | Y | Sensitive to input order | O(n²) |
| Shell Sort | Y | Y | Varies depending on gap sequence used | O(n²) |
| Quick Sort | Y | Y | O(n log n) | Worst: O(n²), Best/Average: O(n log n) |
| Merge Sort | N | Y | O(n log n) | Worst/Best/Average: O(n log n) |
| Heap Sort | Y | Y | O(n log n) | Worst/Best/Average: O(n log n) |
| Counting Sort | N | N | O(n + k) (k is input range) | O(n + k) |
| Radix Sort | N | N | O(dn) (d is number of digits), O(n) (if d is constant) | O(dn), O(n) (if d is constant) |
| Bucket Sort | N | N | O(n) (if data is uniformly distributed) | O(n) (if data is uniformly distributed) |
In-Place Sort
- Refers to sorting algorithms that use only a constant amount of extra space beyond the input array.
- Does not require additional storage proportional to the size of the input data (n).
- Quick Sort, Selection Sort, Bubble Sort, Insertion Sort, Shell Sort, and Heap Sort fall into this category.
- Merge Sort, Counting Sort, Radix Sort, and Bucket Sort are not in-place because they use extra space.
Comparison-Based Sort
- Sorting algorithms that determine the order of elements based on comparisons between key values.
- Includes Selection, Bubble, Insertion, Shell, Quick, Merge, and Heap Sort.
- Counting, Radix, and Bucket Sort use distribution-based logic and are not comparison-based.
Time Complexity
- A measure of algorithm efficiency, describing how execution time increases with input size (n).
- Typically described using worst-case performance.
- Some algorithms like Quick Sort and Merge Sort have different time complexities for best, average, and worst cases.
Average Performance
- Expected performance over all possible inputs.
- For large input sizes, algorithms with better time complexity are generally more efficient.
