User:DrTall/Notes
From The Urban Dead Wiki
Jump to navigationJump to search
List of sorting algorithms
In this table, n is the number of records to be sorted. The columns "Average" and "Worst" give the time complexity in each case, under the assumption that the length of each key is constant, and that therefore all comparisons, swaps, and other needed operations can proceed in constant time. "Memory" denotes the amount of auxiliary storage needed beyond that used by the list itself, under the same assumption. These are all comparison sorts.
| Name | Average | Worst | Memory | Stable | Method | Other notes |
|---|---|---|---|---|---|---|
| Bubble sort | O(n²) | O(n²) | O(1) | Yes | Exchanging | |
| Selection sort | O(n²) | O(n²) | O(1) | No | Selection | Can be implemented as a stable sort |
| Insertion sort | O(n²) | O(n²) | O(1) | Yes | Insertion | Average case is also O(n + d), where d is the number of inversions |
| Binary tree sort | O(n log n) | O(n log n) | O(n) | Yes | Insertion | When using a self-balancing binary search tree |
| Merge sort | O(n log n) | O(n log n) | O(n) | Yes | Merging | |
| Heapsort | O(n log n) | 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; can be O(n log n) worst case if median pivot is used |
| Name | Average | Worst | Memory | Stable | n << 2k | Notes |
|---|---|---|---|---|---|---|
| Bucket sort | O(n·d) | O(n²·d) | O(n·d) | Yes | No | Assumes uniform distribution of elements from the domain in the array. |
| Counting sort | O(n+2d) | O(n+2d) | O(n+2d) | Yes | Yes | |
| Radix sort | O(n·d) | O(n·d) | O(n) | Yes | No |
