User:Nyenyec/tmp alg
| Name | Average | Worst | Memory | Stable | Method | Other notes |
|---|---|---|---|---|---|---|
| Bubble sort | — | O(n²) | O(1) | Yes | Exchanging | Times are for best variant |
| Cocktail sort | — | O(n²) | O(1) | Yes | Exchanging | |
| Comb sort | O(n log n) | O(n log n) | O(1) | No | Exchanging | Small code size |
| Gnome sort | — | O(n²) | O(1) | Yes | Exchanging | |
| Selection sort | O(n²) | O(n²) | O(1) | No | Selection | |
| Insertion sort | O(n + d) | O(n²) | O(1) | Yes | Insertion | d is the number of inversions, which is O(n²) |
| Shell sort | — | O(n log² n) | O(1) | No | Insertion | |
| Binary tree sort | O(n log n) | O(n log n) | O(n) | Yes | Insertion | When using a self-balancing binary search tree |
| Library sort | O(n log n) | O(n²) | O(n) | Yes | Insertion | |
| Merge sort | O(n log n) | O(n log n) | O(n) | Yes | Merging | |
| In-place merge sort | O(n log n) | O(n log n) | O(1) | Yes | Merging | |
| Heapsort | O(n log n) | O(n log n) | O(1) | No | Selection | |
| Smoothsort | — | O(n log n) | O(1) | No | Selection | |
| Quicksort | O(n log n) | O(n²) | O(log n) | No | Partitioning | Naïve variants use O(n) space |
| Introsort | O(n log n) | O(n log n) | O(log n) | No | Hybrid | used in most implementations of STL [citation needed] |
| Patience sorting | — | O(n²) | O(n) | No | Insertion | Finds all the longest increasing subsequences within O(n log n) |
This table describes sorting algorithms that are not comparison sorts. As such, they are not limited by a O(nlog n) lower bound. Complexities below are in terms of n, the number of items to be sorted, k, the size of each key, and s, the chunk size used by the implementation. Many of them are based on the assumption that the key size is large enough that all entries have unique key values, and hence that n << 2k.
| Name | Average | Worst | Memory | Stable | n << 2k? | Notes |
|---|---|---|---|---|---|---|
| Pigeonhole sort | O(n+2k) | O(n+2k) | O(2k) | Yes | Yes | |
| Bucket sort | O(n·k) | O(n²·k) | O(n·k) | Yes | No | Assumes uniform distribution of elements from the domain in the array. |
| Counting sort | O(n+2k) | O(n+2k) | O(n+2k) | Yes | Yes | |
| LSD Radix sort | O(n·k/s) | O(n·k/s) | O(n) | Yes | No | |
| MSD Radix sort | O(n·k/s) | O(n·(k/s)·2s) | O((k/s)·2s) | No | No | |
| Spreadsort | O(n·k/log(n)) | O(n·(k - log(n)).5) | O(n) | No | No | Asymptotics are based on the assumption that n << 2k, but the algorithm does not require this. |