Merge sort, heapsort, Timsort and introsort are O(n log n) in the worst case; quicksort is O(n log n) on average but O(n²) at worst, and insertion sort is O(n²) but O(n) on sorted input. Counting and radix sort beat O(n log n) by reading the values. Python, Java for objects and the V8 engine use Timsort, which is stable. C# uses introsort, as C++ std::sort usually does, and it is not stable.
Best, average and worst case
These are the standard figures for each algorithm, with n items to sort. Extra space is memory beyond the input. A stable sort keeps equal items in their original order, which matters when you sort by one key and then by another.
| Algorithm | Best | Average | Worst | Extra space | Stable |
|---|---|---|---|---|---|
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) stack on average | No |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Counting sort, values up to k | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Yes |
| Radix sort, d digits in base b | O(d · (n + b)) | O(d · (n + b)) | O(d · (n + b)) | O(n + b) | Yes |
| Timsort | O(n) | O(n log n) | O(n log n) | Up to n/2 elements | Yes |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) stack | No |
No sort that only compares pairs of items can beat O(n log n) in the worst case. Counting and radix sort get under it by using the values themselves as positions, which is why they need a limited range of keys. If an interviewer asks whether you can do better than O(n log n), this is usually what they want to hear, along with the condition that makes it possible.
Timsort and introsort
Most built-in sorts are one of these two hybrids, so they are the ones to be able to describe. V8's write-up on adopting Timsort explains it plainly: Timsort, "initially developed by Tim Peters for Python in 2002," is "an adaptive stable Mergesort variant." It scans for runs that are already in order, extends short runs with insertion sort, and merges neighboring runs until one is left. A sorted array is one run, so "already-sorted sequences are sorted in O(n)," and "the worst case is O(n log n)." Its merge buffer "never exceeds n/2," and Java's Javadoc gives the same bound for its version.
Introsort starts as quicksort and protects itself from quicksort's worst case. C#'s List.Sort documentation spells out the rules: insertion sort when a partition has 16 elements or fewer, heapsort "if the number of partitions exceeds 2 log n," and quicksort otherwise. cppreference notes that introsort "can handle all cases with O(N·log(N)) comparisons" and "thus is usually used for implementing sort()." Neither keeps equal elements in order.
Newer libraries use descendants of both. Go's sort package switched to pattern-defeating quicksort in Go 1.19, and Rust's sort_unstable is based on ipnsort and its sort on driftsort. All three keep an O(n log n) worst case while running much faster on input with patterns, such as sorted runs.
Which sort each language uses
Each row is from that language's own documentation, read on November 12, 2026, plus V8's blog for the engine in Chrome and Node.js. Where the documentation names no algorithm or gives no figure, the row says so. The language pages linked below this article have the rest of each library.
| Language and call | Algorithm | Stated cost | Stable |
|---|---|---|---|
| Python: list.sort(), sorted() | Timsort | O(n log n) worst case, and only O(n) comparisons on sorted or reverse-sorted input (cost table) | Yes, guaranteed |
| Java: Arrays.sort on primitives | Dual-Pivot Quicksort | "O(n log(n)) performance on all data sets" | Not stated. Equal primitives cannot be told apart anyway. |
| Java: Arrays.sort on objects, List.sort, Collections.sort | Adaptive iterative mergesort, "adapted from Tim Peters's list sort for Python" | About n comparisons on nearly sorted input. Temporary storage up to n/2 references. | Yes, guaranteed |
| JavaScript: Array.prototype.sort | Not specified. V8, in Chrome and Node.js, uses Timsort. | None: it "cannot be guaranteed as it depends on the implementation" | Yes, required since ECMAScript 2019 |
| C++: std::sort | Not specified. Usually introsort. | O(N log N) comparisons | No |
| C++: std::stable_sort | Not specified | N log N comparisons with enough extra memory, otherwise at most N log² N | Yes |
| C#: Array.Sort, List<T>.Sort | Introsort | O(n log n) | No |
| C#: Enumerable.OrderBy | Not stated | Not stated | Yes |
| Go: sort.Sort, sort.Slice | Pattern-defeating quicksort (Go 1.19) | O(n*log(n)) calls to Less and Swap, stated for sort.Sort | No |
| Go: sort.Stable | Not stated | O(n*log(n)) calls to Less and O(n*log(n)*log(n)) calls to Swap | Yes |
| Rust: slice::sort | Driftsort | O(n * log(n)) worst case, linear on sorted or reversed input | Yes |
| Rust: slice::sort_unstable | Ipnsort | O(n * log(n)) worst case, in place | No |
The JavaScript row is the one to remember. The specification requires a stable sort but gives no complexity and leaves the sequence of comparisons to the engine, so "O(n log n)" for sort in JavaScript is a statement about V8 and the other engines, not about the language.
When not to sort
Sorting first is often right, and O(n log n) is fast enough for most interview inputs. These are the cases where it is more than you need:
- The k largest or smallest items: a heap of size k costs O(n log k), less than sorting everything when k is small. See heaps and priority queues.
- The single kth item: quickselect averages O(n). Rust's
select_nth_unstableis documented as O(n) and in place. - Small integer keys: counting sort is O(n + k), linear when the range k is close to n.
- Only a minimum or a maximum: one pass, O(n).
- Data that arrives one item at a time and must stay ordered: a balanced tree or a heap, not a sort after every insert.
Common interview traps
JavaScript's default sort is the classic one. MDN says the default order is "built upon converting the elements into strings," so numbers sort as text:
JavaScript
[10, 9, 1].sort(); // [1, 10, 9]: compared as strings
[10, 9, 1].sort((a, b) => a - b); // [1, 9, 10]Stability is the second. A stable sort lets you sort by the less important key first and the more important key second, and ties on the second keep the order of the first. With an unstable sort, such as C++ std::sort or C# List.Sort, that second pass can scramble the first. In Python both passes are safe:
people = [("ana", 31), ("ben", 25), ("cy", 31), ("di", 25)]
# By age, and by name within each age: two stable sorts, least important key first.
people.sort(key=lambda p: p[0]) # name
people.sort(key=lambda p: p[1]) # age; equal ages keep name order
# [('ben', 25), ('di', 25), ('ana', 31), ('cy', 31)]
# Counting sort for small non-negative integers: O(n + k), no comparisons.
def counting_sort(values, k):
counts = [0] * (k + 1)
for v in values:
counts[v] += 1
out = []
for v, c in enumerate(counts):
out.extend([v] * c)
return outThe third is sorting inside a loop. Sorting once and then making one pass is O(n log n); sorting on every iteration is O(n² log n), and it is easy to write without noticing when the sort is hidden in a helper.
How to say it out loud
I'll sort the intervals by start time first, which is O(n log n), and then merge them in one pass, so O(n log n) overall and O(n) for the output. Python's sort is Timsort, so if the input is already mostly sorted it'll be closer to linear, but I'll quote the worst case.
I don't need the whole array sorted, only the ten largest values, so I'll keep a min-heap of size ten. That's O(n log k) instead of O(n log n), and O(k) extra space.
Naming the algorithm your language uses and whether it is stable takes one sentence and answers the follow-up before it is asked. Practice it in a coding mock interview, and see the Big O cheat sheet for the costs of the data structures.
Complexity by language
Each language page takes its figures from that language's own documentation, cites it, and says what the documentation leaves out. TypeScript runs as JavaScript, so its costs are on the JavaScript page.
For the structures and algorithms themselves, see the Big O cheat sheet and sorting algorithm complexity.
Frequently asked questions
What sorting algorithm does Python use?
Timsort, according to Python's sorting how-to. It is guaranteed to be stable, and Python's cost table gives O(n log n) in the worst case and only O(n) comparisons on input that is already sorted or reverse-sorted.
What is the time complexity of JavaScript's sort?
The language does not say. The specification requires the sort to be stable but leaves the sequence of comparisons to the engine, and MDN says its complexity cannot be guaranteed. V8, the engine in Chrome and Node.js, uses Timsort, which is O(n log n) in the worst case.
Which sorting algorithms are stable?
Merge sort, insertion sort, counting sort, radix sort and Timsort are stable. Quicksort, heapsort and introsort are not. Among built-ins, Python's sort, Java's object sorts, JavaScript's sort, C# OrderBy, C++ stable_sort and Rust's sort are stable, while C++ std::sort, C# List.Sort and Rust's sort_unstable are not.
Can a sort be faster than O(n log n)?
Not if it only compares pairs of items: O(n log n) comparisons is the worst-case lower bound. Counting sort and radix sort avoid comparisons by using the values as positions, so they run in O(n + k) and O(d times (n + b)) when the range of keys is limited.