Here is a table for common sorting algorithms. | **Algorithm** | **Time Complexity** | **Space Complexity** | **Stable?** | |------------------------------|-----------------------------|----------------------|------------| | [Bubble Sort](https://en.wikipedia.org/wiki/Bubble_sort) | Worst: O(n^2)
Avg: O(n^2) | O(1) | Yes | | [Selection Sort](https://en.wikipedia.org/wiki/Selection_sort) | Worst: O(n^2)
Avg: O(n^2) | O(1) | No | | [Insertion Sort](https://en.wikipedia.org/wiki/Insertion_sort) | Worst: O(n^2)
Avg: O(n^2) | O(1) | Yes | | [Merge Sort](https://en.wikipedia.org/wiki/Merge_sort) | Worst: O(n log n)
Avg: O(n log n) | O(n) | Yes | | [Quick Sort](https://en.wikipedia.org/wiki/Quicksort) | Worst: O(n^2)
Avg: O(n log n) | O(log n) to O(n) | No (simple version) | | [Heap Sort](https://en.wikipedia.org/wiki/Heapsort) | Worst: O(n log n)
Avg: O(n log n) | O(1) | No | | [Counting Sort](https://en.wikipedia.org/wiki/Counting_sort) | Worst: O(n+k)
Avg: O(n+k) | O(k) | Yes | | [Bucket Sort](https://en.wikipedia.org/wiki/Bucket_sort) | Worst: O(n^2)
Avg: O(n) | O(n) | Yes (with linked lists) | | [Radix Sort](https://en.wikipedia.org/wiki/Radix_sort) | Worst: O(d(n+k))
Avg: O(d(n+k)) | O(n+k) | Yes | | [Shell Sort](https://en.wikipedia.org/wiki/Shellsort) | Worst: O(n(log n)^2)
Avg: Depends on gap sequence | O(1) | No | | [Tim Sort](https://en.wikipedia.org/wiki/Timsort) | Worst: O(n log n)
Avg: O(n log n) | O(n) | Yes | Fun fact, Chrome uses Timsort for `Array.prototype.sort()` and it was not stable until Chrome 70 ([ref](https://v8.dev/blog/array-sort)).

掲示板 (17)