| Sequence | Duplicate | Direction |
|---|---|---|
| Increasing | no | Ascending |
| Decreasing | no | Descending |
| Non-decreasing | yes | Ascending |
| Non-increasing | yes | Descending |
Comparison based algorithm
- Make at least nlog2(n) comparisons on average
InsertionSort
STL Sort
SelectionSort
CountSort
Info
Simple & inefficient: InsertionSort, BubbleSort, SelectionSort
O(n^2) algorithm
Efficient: MergeSort, QuickSort, HeapSort:
HeapSort is based on heap data structure
O(n Logn) algorithm
Distribution-based techniques: CountingSort, BucketSort, RadixSort
What if the value is in range /[0, 100/]