Algoritma penyortiran
Perbandingan Algortima

Pada tabel ini, n merupakan angka dari rekord yang akan diurut. Kolom "Average" dan "Worst" memberikan kompleksitas waktu pada setiap case, dengan asumsi panjang setiap nilai merupakan konstan, dan oleh karena segala perbandingannya, penukarannya, dan segala operasi yang dibutuhkan dapat diproses pada waktu konstan. "Memori" menunjukkan jumlah dari simpanan tambahan dibutuhkan yang digunakan oleh list ini sendiri. Segala Sorting Pembangding ini. Waktu kalkulasi dan memori dari algoritme dapat diukur menggunakan notasi beragam seperti theta, omega, Big-O, small-o, dll. Memori dan waktu kalkulasi dibawah dapat diaplikasikan pada semua dari 5 notasi dibawah.
| Name | Best | Average | Worst  | Memory | Stable | Method  | Other notes  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Quicksort | 20  {\mathcal {}}n\log n | 20  {\mathcal {}}n\log n | 25  {\mathcal {}}n^{2} | 05  {\mathcal {}}\log n | Depends | Partitioning | Quicksort is usually done in place with O(log(n)) stack space.[butuh rujukan]  Most implementations are unstable, as stable in-place partitioning is more complex. Naïve variants use an O(n) space array to store the partition.[butuh rujukan]  |
| Merge sort | 20  {\mathcal {}}{n\log n} | 20  {\mathcal {}}{n\log n} | 20  {\mathcal {}}{n\log n} | 15 Depends; worst case is  {\mathcal {}}n | Yes | Merging | Highly parallelizable (up to O(log(n))) for processing large amounts of data. |
| In-place Merge sort | 50  {\mathcal {}}- | 50  {\mathcal {}}- | 23  {\mathcal {}}{n\left(\log n\right)^{2}} | 00  {\mathcal {}}{1} | Yes | Merging | Implemented in Standard Template Library (STL); can be implemented as a stable sort based on stable in-place merging. |
| Heapsort | 20  {\mathcal {}}{n\log n} | 20  {\mathcal {}}{n\log n} | 20  {\mathcal {}}{n\log n} | 00  {\mathcal {}}{1} | No | Selection |  |
| Insertion sort | 15  {\mathcal {}}n | 25  {\mathcal {}}n^{2} | 25  {\mathcal {}}n^{2} | 00  {\mathcal {}}{1} | Yes | Insertion | O(n + d), where d is the number of inversions |
| Introsort | 20  {\mathcal {}}n\log n | 20  {\mathcal {}}n\log n | 20  {\mathcal {}}n\log n | 05  {\mathcal {}}\log n | No | Partitioning & Selection | Used in several STL implementations |
| Selection sort | 25  {\mathcal {}}n^{2} | 25  {\mathcal {}}n^{2} | 25  {\mathcal {}}n^{2} | 00  {\mathcal {}}{1} | No | Selection | Stable with O(n) extra space, for example using lists. Used to sort this table in Safari or other Webkit web browser. |
| Timsort | 15  {\mathcal {}}{n} | 20  {\mathcal {}}{n\log n} | 20  {\mathcal {}}{n\log n} | 15  {\mathcal {}}n | Yes | Insertion & Merging |  {\mathcal {}}{n} comparisons when the data is already sorted or reverse sorted. |
| Shell sort | 15  {\mathcal {}}n | 23  {\mathcal {}}n(\log n)^{2}  or   {\mathcal {}}n^{3/2} | 23 Depends on gap sequence; best known is  {\mathcal {}}n(\log n)^{2} | 00  {\mathcal {}}1 | No | Insertion |  |
| Bubble sort | 15  {\mathcal {}}n | 25  {\mathcal {}}n^{2} | 25  {\mathcal {}}n^{2} | 00  {\mathcal {}}{1} | Yes | Exchanging | Tiny code size |
| Binary tree sort | 15  {\mathcal {}}n | 20  {\mathcal {}}{n\log n} | 20  {\mathcal {}}{n\log n} | 15  {\mathcal {}}n | Yes | Insertion | When using a self-balancing binary search tree |
| Cycle sort | 50 — | 25  {\mathcal {}}n^{2} | 25  {\mathcal {}}n^{2} | 00  {\mathcal {}}{1} | No | Insertion | In-place with theoretically optimal number of writes |
| Library sort | 50 — | 20  {\mathcal {}}{n\log n} | 25  {\mathcal {}}n^{2} | 15  {\mathcal {}}n | Yes | Insertion |  |
| Patience sorting | 50 — | 50 — | 20  {\mathcal {}}n\log n | 15  {\mathcal {}}n | No | Insertion & Selection | Finds all the longest increasing subsequences within O(n log n) |
| Smoothsort | 15  {\mathcal {}}{n} | 20  {\mathcal {}}{n\log n} | 20  {\mathcal {}}{n\log n} | 00  {\mathcal {}}{1} | No | Selection | An adaptive sort -  {\mathcal {}}{n} comparisons when the data is already sorted, and 0 swaps. |
| Strand sort | 15  {\mathcal {}}n | 25  {\mathcal {}}n^{2} | 25  {\mathcal {}}n^{2} | 15  {\mathcal {}}n | Yes | Selection |  |
| Tournament sort | 50 — | 20  {\mathcal {}}n\log n | 20  {\mathcal {}}n\log n |  |  | Selection |  |
| Cocktail sort | 15  {\mathcal {}}n | 25  {\mathcal {}}n^{2} | 25  {\mathcal {}}n^{2} | 00  {\mathcal {}}{1} | Yes | Exchanging |  |
| Comb sort | 15  {\mathcal {}}n | 15  {\mathcal {}}n\log n | 25  {\mathcal {}}n^{2} | 00  {\mathcal {}}{1} | No | Exchanging | Small code size |
| Gnome sort | 15  {\mathcal {}}n | 25  {\mathcal {}}n^{2} | 25  {\mathcal {}}n^{2} | 00  {\mathcal {}}{1} | Yes | Exchanging | Tiny code size. |
| UnShuffle Sort | 15  kN | 25  kN | 25  kN | 00 In place for linked lists. N*sizeof(link) for array. | Can be made stable by appending the input order to the key. | Distribution and Merge | No exchanges are performed. Performance is independent of data size. The constant 'k' is proportional to the entropy in the input. K = 1 for ordered or ordered by reversed input so runtime is equivalent to checking the order O(N). |
| Franceschini's method | — | 20  n\log n | 20  n\log n | 00  1 | Yes | ? |  |
| Block sort | 15  n | 25  n\log n | 25  n\log n | 00  1 | Yes | Insertion & Merging | Combine a block-based O(n) in-place merge algorithm with a bottom-up merge sort. Turns into a full-speed merge sort if additional memory is optionally provided to it. |
| Bogosort | 15  {\mathcal {}}n | 45  {\mathcal {}}n\cdot n! | 45  {\mathcal {}}{n\cdot n!\to \infty } | 00  {\mathcal {}}{1} | No | Luck | Randomly permute the array and check if sorted. |
|  | 50  {\mathcal {}}- | 20  {\mathcal {}}n\log n | 20  {\mathcal {}}{n\log n} | 00  {\mathcal {}}{1} | Yes |  |  |