You Already Don't Understand Your Code ====================================== By George Mandis https://george.mand.is/2026/10/you-already-dont-understand-your-code Wednesday, October 28th 2026 ![A cross-section of geological strata. On the surface a person sits on the grass with a laptop, next to a cat, under a hovering UFO. Each layer below holds an older era of computing: laptops, phones and cloud icons, then punch cards and JavaScript, then operating-system logos, then mainframes and chips, then vacuum tubes and circuit boards, and at the bottom an abacus, binary digits and a dinosaur fossil.](/media/you-already-dont-understand-your-code.jpg) The title is intentionally provocative :) You probably do understand your code. Or at least, I'm sure you think you do. I like to think I do too! But before we go any deeper into the premise behind the title, let's play a fun little game. Do you think you understand the code below? **Python** ```python nums = [5, 3, 10, 1, 9] words = ["pear", "Apple", "fig", "banana"] print(sorted(nums)) # [1, 3, 5, 9, 10] print(sorted(words)) # ['Apple', 'banana', 'fig', 'pear'] ``` **Java** ```java int[] nums = {5, 3, 10, 1, 9}; String[] words = {"pear", "Apple", "fig", "banana"}; Arrays.sort(nums); // [1, 3, 5, 9, 10] Arrays.sort(words); // [Apple, banana, fig, pear] ``` **C** ```c int cmp(const void *a, const void *b) { return *(int*)a - *(int*)b; } int nums[] = {5, 3, 10, 1, 9}; qsort(nums, 5, sizeof(int), cmp); // 1 3 5 9 10 ``` **C++** ```cpp std::vector nums = {5, 3, 10, 1, 9}; std::vector words = {"pear", "Apple", "fig", "banana"}; std::sort(nums.begin(), nums.end()); // 1 3 5 9 10 std::sort(words.begin(), words.end()); // Apple banana fig pear ``` **Go** ```go nums := []int{5, 3, 10, 1, 9} words := []string{"pear", "Apple", "fig", "banana"} slices.Sort(nums) // [1 3 5 9 10] slices.Sort(words) // [Apple banana fig pear] ``` **Rust** ```rust let mut nums = vec![5, 3, 10, 1, 9]; let mut words = vec!["pear", "Apple", "fig", "banana"]; nums.sort(); // [1, 3, 5, 9, 10] words.sort(); // ["Apple", "banana", "fig", "pear"] ``` **Ruby** ```ruby [5, 3, 10, 1, 9].sort # => [1, 3, 5, 9, 10] ["pear", "Apple", "fig", "banana"].sort # => ["Apple", "banana", "fig", "pear"] ``` **Swift** ```swift let nums = [5, 3, 10, 1, 9].sorted() // [1, 3, 5, 9, 10] let words = ["pear", "Apple", "fig", "banana"].sorted() // ["Apple", "banana", "fig", "pear"] ``` **PHP** ```php $nums = [5, 3, 10, 1, 9]; $words = ["pear", "Apple", "fig", "banana"]; sort($nums); // [1, 3, 5, 9, 10] sort($words); // ["Apple", "banana", "fig", "pear"] ``` **C#** ```csharp int[] nums = {5, 3, 10, 1, 9}; string[] words = {"pear", "Apple", "fig", "banana"}; Array.Sort(nums); // 1 3 5 9 10 Array.Sort(words); // Apple banana fig pear ``` Okay, you might not know all of these languages fluently, but you could probably follow that these are all different ways of sorting lists (or arrays, or vectors, or slices, or whatever the language calls the concept of a collection of data). You're smart like that. That's why I like you. I'd say, given just the programs we've shared so far, you might even feel like you could say you "understand" the code, even if it's not in a language you're particularly comfortable in. Now a more interesting question—could you tell me which implementation is faster, and why? The answer is always some flavor of "it depends." But I could tell you pretty definitively that Python is going to be faster than C++ here, in a [Big-O](https://en.wikipedia.org/wiki/Big_O_notation) sense, when the list you hand it is already sorted or nearly sorted. Think of appending a few rows to an already-ordered log and sorting the whole thing again. (Reality tends to wash a lot of this out and make it not matter. A million already-sorted integers in C++ still finishes before you can blink.) Why is that? Because Python's `sorted()` uses [Timsort](https://en.wikipedia.org/wiki/Timsort), which notices runs that are already in order and finishes in O(n) on sorted input, while C++'s `std::sort` uses [introsort](https://en.wikipedia.org/wiki/Introsort), a [quicksort](https://en.wikipedia.org/wiki/Quicksort) hybrid that does its full O(n log n) of work whether the input needed it or not. I was curious and measured it: on a sorted array of a million integers, Python's sort makes 999,999 comparisons. [GCC's](https://gcc.gnu.org/onlinedocs/libstdc++/) `std::sort` makes 25.6 million. Except... I wrote that paragraph, went to check it on my Mac, and it was wrong! Apple's clang ships a different C++ standard library, [LLVM's libc++](https://libcxx.llvm.org/), whose [introsort](https://github.com/llvm/llvm-project/blob/main/libcxx/include/__algorithm/sort.h) notices when a partition comes out already ordered and finishes with a bounded insertion pass. Two million comparisons. Linear. Same `std::sort`, same source file, different answer, depending on which compiler happened to be on the machine. Here's the thing to takeaway though: of those ten snippets—all running some flavor of a stock sorting function or method on two different sets of data—no two run the same algorithm. Hold that thought. We'll come back to it. Let's try a harder one: ```javascript // Example 1 var scores = new Array(40, 100, 1, 5, 25, 10); scores.sort(function (a, b) { return a - b; }); ``` ```javascript // Example 2 var scores = new Array(40, 100, 1, 5, 25, 10); scores.sort(function (a, b) { return a - b; }); ``` ```javascript // Example 3 var scores = new Array(40, 100, 1, 5, 25, 10); scores.sort(function (a, b) { return a - b; }); ``` ```javascript // Example 4 var scores = new Array(40, 100, 1, 5, 25, 10); scores.sort(function (a, b) { return a - b; }); ``` ```javascript // Example 5 var scores = new Array(40, 100, 1, 5, 25, 10); scores.sort(function (a, b) { return a - b; }); ``` ```javascript // Example 6 var scores = new Array(40, 100, 1, 5, 25, 10); scores.sort(function (a, b) { return a - b; }); ``` ```javascript // Example 7 var scores = new Array(40, 100, 1, 5, 25, 10); scores.sort(function (a, b) { return a - b; }); ``` ```javascript // Example 8 var scores = new Array(40, 100, 1, 5, 25, 10); scores.sort(function (a, b) { return a - b; }); ``` ```javascript // Example 9 var scores = new Array(40, 100, 1, 5, 25, 10); scores.sort(function (a, b) { return a - b; }); ``` ```javascript // Example 10 var scores = new Array(40, 100, 1, 5, 25, 10); scores.sort(function (a, b) { return a - b; }); ``` Okay, you probably feel even more confident you understand this code. (Sincerely though—why is that?). Or you might think [copy/paste](https://clipboard.cat) is broken on my machine and I published this without proofreading. It looks like the same code snippet copied ten-times over. To many of you, you probably clocked that as a classic JavaScript sort. It's looked the same since 1997. You even remembered the comparator, so you've clearly been bitten before! Omit it and every engine since 1997 will hand you back `1, 10, 100, 25, 40, 5`, which is how nobody has ever sorted anything ever, because the default compares everything as strings. That one line has been true for thirty (!!) years and still catches people every week. But you knew that. You understand this code. Now can you tell me... which one is faster? ... Oh wait, I cheated a little bit. I forgot to mention some things: - **Example 1** is running in Internet Explorer 4, in 1997, on JScript. Nobody outside Microsoft knows what algorithm it used, but it was [stable](https://en.wikipedia.org/wiki/Sorting_algorithm#Stability). Mozilla's engineers later cited IE's stable sort as [a reason to fix their own](https://bugzilla.mozilla.org/show_bug.cgi?id=224128#c4). - **Example 2** is running in Netscape 4, in 1999, on SpiderMonkey. Quicksort. Not stable. - **Example 3** is running in Mozilla, in 2002, on SpiderMonkey. [Heapsort](https://en.wikipedia.org/wiki/Heapsort). A [bug filed in September 2001](https://bugzilla.mozilla.org/show_bug.cgi?id=99120) complained that quicksort choked on already-sorted input, and in March 2002 Brendan Eich landed a patch to "switch from QuickSort to heap-sort." Still not stable. - **Example 4** is running in Firefox 3, from 2008 through today, on SpiderMonkey. [Merge sort](https://en.wikipedia.org/wiki/Merge_sort): [insertion sort](https://en.wikipedia.org/wiki/Insertion_sort) on small blocks, then a [non-recursive merge](https://searchfox.org/firefox-main/source/js/src/ds/Sort.h). The patch was [first posted in November 2003](https://bugzilla.mozilla.org/show_bug.cgi?id=224128), sat for three years over memory concerns, landed on trunk in October 2006 and shipped in Firefox 3. Stable. - **Example 5** is running in Safari, from 2015 through today, and in Bun since 2022, on JavaScriptCore. Merge sort, implemented in JavaScript inside the engine. A [2022 WebKit ticket](https://bugs.webkit.org/show_bug.cgi?id=239267) filed by one of its own engineers describes it as "a fairly naive merge sort." Stable. The road there is my favorite in this list. In May 2008, people.com crashed Safari by shuffling an array with `sort(function() { return 0.5 - Math.random(); })`, which the C++ standard library's sort could not survive, so WebKit [started sorting](https://commits.webkit.org/26483@main) custom-comparator arrays by inserting them into an [AVL tree](https://en.wikipedia.org/wiki/AVL_tree). Over the next seven years the C++ grew into a sort that [picked](https://github.com/WebKit/WebKit/commit/d9d3a5d8f416551b9b238bca1cf1e445ab05ec3a) merge sort for strings, `qsort` for numbers, the AVL tree for custom comparators, and a [selection sort](https://en.wikipedia.org/wiki/Selection_sort) for anything that wasn't a plain array. In 2015 a WebKit engineer threw the whole thing out with a commit titled ["It shouldn't take 1846 lines of code and 5 FIXMEs to sort an array"](https://commits.webkit.org/162412@main) and rewrote it as the merge sort you get today. - **Example 6** is running in Chrome 1 through 69, and Node 0.x through 10, on V8. Insertion sort for arrays of 10 or fewer elements, quicksort above that. Not stable. Which means this exact six-element array ran insertion sort, and the day your scores list grew to eleven items it silently became quicksort. Stable in your tests, unstable in production. - **Example 7** is running in Internet Explorer 9 through legacy Edge, on Chakra. Insertion sort up to 512 elements, then quicksort. Not stable until a merge sort landed in November 2018. - **Example 8** is running in Chrome 70+, Node 11+, Deno, Electron and Cloudflare Workers, on V8. Timsort, written in Torque. Stable. - **Example 9** is running in a React Native app, on Hermes. Quicksort. In 2020 the Hermes team made it stable by keeping a side array of each element's original index and using it as the tiebreaker. If your comparator *grew* the array mid-sort, the index array didn't grow with it, and the sort read past the end of the heap. A bug-bounty researcher found it within six days of the change, before it reached a public release, and Meta's security team later [wrote it up](https://engineering.fb.com/2022/07/20/security/hermes-quicksort-to-run-doom/) by building a full exploit chain out of the out-of-bounds swaps and using it to run Doom inside the JavaScript engine. Stable, after the fix. - **Example 10** is running in QuickJS, the embedded engine. Its own introsort-style quicksort, `rqsort`, with an index tiebreak to fake stability. (And I left one out. Rhino, JavaScript on the JVM, started with quicksort in 1999, [switched to heapsort in January 2002](https://github.com/mozilla/rhino/commit/aeaf4c095c4f8cebcc43a13242102e5d78da05e9) "to follow JS," and since [2007](https://bugzilla.mozilla.org/show_bug.cgi?id=399348) just hands the array to Java's `Arrays.sort`. Which is Timsort. Which is Java's port of Python's algorithm. JavaScript, sorted by Java, using Python's idea.) So the answer to which JavaScript sort is faster comes down to some combination of where it executed and when in history. The code you wrote in 1999, left untouched and executing god knows what today on some cute little esoteric corner of the web, is almost certainly fundamentally different under the hood. If it lived in the Netscape lineage, it started as quicksort in 1999, took a detour through heapsort in 2002 and has been running merge sort since Firefox 3 in 2008. If it lived in Chrome, it was insertion sort or quicksort (depending on the size of your array!) for a decade and has been Timsort since September 2018. My favorite version of this is Node 10 and Node 11: same program, same company, one release apart, different algorithm. Provided, of course, that nobody has since opened it on a phone, inside a React Native app, or on a Cloudflare Worker. June 2019 was an interesting time in sort history. ES2019 made `Array.prototype.sort` stable at the spec level. Before that the spec said outright that the sort didn't need to be. V8 got there in September 2018, closing what its own team calls one of the oldest tickets in its tracker, and Chakra was the last major holdout. For about twenty years before that, your code didn't change. Your understanding of it probably didn't change either. The thing underneath did, repeatedly. But you still "understood the code" along the way there... right? And it's not entirely settled even now. The spec says what order the results come out in. It says nothing about the order the comparisons happen in. Hand any of those ten modern engines a comparator with a side effect, a counter or a log line or a mutation, and you can watch them disagree with one another today. I really could not get enough of this and kept digging. Here are some other languages have had similar journeys: - **Swift** used introsort through Swift 4 and switched to a modified Timsort in Swift 5, in 2019. The sort is stable in practice. The documentation refuses to promise it. This one is particularly funny to me: the algorithm is stable, the engineers know it's stable, and the docs say don't count on it. - **C**'s `qsort` in glibc is a merge sort, and has been for decades. In October 2023 its maintainers ripped the merge sort out in favor of introsort. Programs that had quietly come to depend on stability broke (the reinstatement commit calls it "an instance of Hyrum's law"), the introsort turned out to be no faster, and in January 2024, sixteen days before glibc 2.39 shipped, the merge sort went back in. The introsort never reached a release. Meanwhile Qualys found a memory-corruption bug in the quicksort fallback that had been there since 1992. The C standard requires no particular algorithm at all. The name is a lie. - **Rust** swapped both of its sorts in September 2024. `sort` went from a Timsort derivative to driftsort, and `sort_unstable` went from [pdqsort](https://en.wikipedia.org/wiki/Introsort#pdqsort) to ipnsort (Kudos to Rust here for putting `unstable` in the name). - **Go**'s `sort.Ints` was an introsort-style quicksort until Go 1.19 in 2022, when it became pattern-defeating quicksort. - **Python** has run Timsort since 2002, but 3.11 quietly replaced its merge policy with [Powersort](https://en.wikipedia.org/wiki/Powersort). - **PHP 7**'s `sort()` was accidentally stable for arrays of 16 or fewer elements and unstable for larger ones. (Sound familiar?) PHP 8.0 added an index tiebreak to make it honest. - **Java** sorts an `int[]` with [Dual-Pivot Quicksort](https://en.wikipedia.org/wiki/Quicksort#Multi-pivot_quicksort) and an `Integer[]` with Timsort. Same JDK, same method name, different algorithm. The honest answer to "what does `sort` do in Java?" is "which `sort`?" - **C#** used a plain quicksort until .NET Framework 4.5 and introsort since. - **Ruby**'s `Array#sort` is whatever your C library's `qsort_r` is. On Linux that's glibc's merge sort. On macOS it's a Bentley-McIlroy quicksort with a heapsort fallback, inherited from FreeBSD. Ruby's own hand-rolled quicksort only runs where neither exists. The docs hedge with "may be unstable," which on Linux it mostly isn't. Here's the whole table for the ten snippets up top: | Language, call | Algorithm under the hood | Stable? | Since | | --- | --- | --- | --- | | Python `sorted()` | Timsort, with Powersort merge policy | Yes | 2002; Powersort in 3.11 (2022) | | Java `Arrays.sort(int[])` | Dual-Pivot Quicksort | No | Java 7 (2011) | | Java `Arrays.sort(Object[])` | Timsort | Yes | Java 7 (2011) | | C `qsort()` (glibc) | Merge sort, heapsort fallback if the buffer allocation fails | In practice | Reinstated Jan 2024, before 2.39 shipped | | C++ `std::sort` | Introsort | No | The standard names no algorithm, only an O(n log n) bound, which libc++ didn't meet until LLVM 14 in 2022 | | Go `slices.Sort` | Pattern-defeating quicksort | No | Go 1.19 (2022) | | Rust `slice::sort` | driftsort | Yes | Rust 1.81 (2024) | | Ruby `Array#sort` | Your libc's `qsort_r`: glibc merge sort on Linux, FreeBSD-style introsort on macOS, own quicksort elsewhere | Depends on your OS. Docs say "may be unstable" | Depends on your OS | | Swift `sorted()` | Modified Timsort | In practice, not promised | Swift 5 (2019) | | PHP `sort()` | Hybrid quicksort with an index tiebreak | Yes | PHP 8.0 (2020) | | C# `Array.Sort` | Introsort | No | .NET 4.5 (2012) | ## What is the point of all this? To the extent that the history of computing and programming is a history of abstractions piled on-top of abstractions, each one a deliberate trade of direct understanding for leverage, the LLM/AI transition we are living through today is just the latest chapter. One that's an order of magnitude leap in abstraction, but the same bargain nonetheless. In many circles there are conversations happening and concerns being raised about whether or not we are writing code we still understand. These are good conversations for to have! We should be having them. But I think it's also worth revisiting and recalibrating our sense of what *understanding* even means or ever meant. If you insist that every line of code must be understood, I am going to insist your own software has always depended on layers you almost certainly never personally examined. That, on some level—and in the least accusatory way possible—you never fully understood it. And that is okay! What we are circling here is where to draw the line. There are still real differences between understanding an interface, understanding a system's behavior, being able to reason about how it fails, and merely having watched it succeed on the happy path. So let me say the uncomfortable half plainly: it is fine that we don't fully understand the code we're writing with AI today, because we *never* understood it as well as we thought we did. We have always built things we couldn't explain all the way down. There are many layers of understanding between throwing out code like incantations until you get results and being able to perform brain surgery on the rocks we have tricked into thinking. Understanding is not obsolete, but *complete* understanding was never the baseline. AI doesn't introduce the gap between what we can build and what we can comprehend. It moves the boundary. The line has almost certainly moved, and we are (collectively as an industry, as teams, as individuals) trying to figure out where the line should be. Like the history of every other decision in tech, where that line sits "depends" on many things. One thing I am feeling with confidence lately, though: we overestimate how well we understand the code we have already written (without AI). We always have. Nothing in the examples above involved an LLM. That was us, typing `sort()` by hand and shipping an algorithm we couldn't name for twenty years, while feeling like we understood it the whole time. We understood it at a particular level of abstraction. The layers beneath were always somebody else's problem, something we chose not to think about or simple never considered. You don't understand every instruction your compiler emits. You don't understand every operation your database performs. You don't understand every line of your runtime. You probably don't understand every line of your own code six months after you wrote it. And yet you build things, often very successfully. (To that one person reading the last paragraph and saying "I do!" as each turn—congrats. Sit down and have a cookie.) To be clear, I'm *not* suggesting we need to understand every implementation detail of the software we use, or that relying on abstractions is some kind of failure. Quite the opposite! Abstraction is how *any* of this works at all (gestures around at society, technology and progress generally). Nobody should have paused building a 1999 web page to audit SpiderMonkey's pivot selection. What I *am* suggesting is that we're not very good at telling the difference between understanding a system well enough to use it and understanding it as thoroughly as we think we do. We never have been. Those two kinds of "understanding" feel identical from the inside, which makes the edges of what we actually know very hard to see. The hubris isn't in the leaning. It's in mistaking the first kind of understanding for the second, and in drawing the boundary of "understanding" wherever happened to be comfortable. It's a benign hubris, mostly, though one software engineering feels particularly afflicted by. History seems to begin at whatever level of abstraction we happened to arrive at. Everything below it is settled infrastructure we feel entitled to ignore, and everything that arrives after is an affront to the natural order. (I kid, but also, as I age, I feel this.) I want to end this softly, with a call for all of us to find our own way in this new world, to find the level of abstraction we are comfortable engaging with, and to be a little more honest about where our understanding of it ends. That "it depends." But I do also want to plant a strong opinion in the archives: the history of computing is a continued, rapid accumulation of these abstractions. Giants on the shoulders of giants on skyscrapers housing more giants. I think the future of making things with computers—notice I didn't just say programming?—professionally, at scale, meaningfully and at "the edge" of... whatever it is tech seems to think it is perpetually on the precipice of, besides a cresting wave of money... without leaning into these abstractions is going to be very, very difficult. The abstraction tides are rising, the layers are getting stranger, and the gap between what we can build and what we can fully comprehend is about to get a lot more interesting. ## Sources Everything above was checked against a primary source where I could find one. Dates are the dates the changes landed, best I could suss out, not when it was first discussed. This was kind of fun to research because reality is kooky! :) If you see any overtly embarassing mistakes, please don't hesitate to write (I appreciate it). I'll try my best to update.
The ten languages - Python: Timsort was [written by Tim Peters in 2002 for Python 2.3](https://en.wikipedia.org/wiki/Timsort). The switch to the Powersort merge strategy is [bpo-34561](https://github.com/python/cpython/issues/78742), opened by Peters in 2018 and landed in September 2021, in time for 3.11. The current strategy is described in CPython's [listsort.txt](https://github.com/python/cpython/blob/main/Objects/listsort.txt). - Java: the [Java 7 `Arrays` javadoc](https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html) carries both implementation notes: Dual-Pivot Quicksort "by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch" for `int[]`, and for `Object[]` a stable mergesort "adapted from Tim Peters's list sort for Python." - C: glibc [removed the merge sort](https://sourceware.org/git/?p=glibc.git;a=commit;h=03bf8357e8291857a435afcc3048e0b697b6cc04) on October 3, 2023 and [reinstated it](https://sourceware.org/git/?p=glibc.git;a=commit;h=709fbd3ec3595f2d1076b4fec09a739327459288) on January 15, 2024, citing Hyrum's law and no speed gain. glibc 2.39 [shipped January 31, 2024](https://sourceware.org/pipermail/libc-announce/2024/000038.html). The [Qualys advisory](https://www.qualys.com/2024/01/30/qsort.txt) of January 30, 2024 says all versions "from at least September 1992 (glibc 1.04) to the current release (glibc 2.38) are affected." The Fedora mass rebuild was blocked on the regression on January 23, 2024: [Red Hat bug 2259845](https://bugzilla.redhat.com/show_bug.cgi?id=2259845), in which Ruby's test suite began corrupting the heap because `sort_by` mutates the array while glibc's `qsort_r` is still sorting it. Florian Weimer's note to the Fedora devel list calling it a blocker survives on [mail-archive.com](https://www.mail-archive.com/devel@lists.fedoraproject.org/msg196885.html) (a mirror). - C++, which library: LLVM's [libc++ project page](https://libcxx.llvm.org/) states it "has become the default C++ Standard Library implementation for many major platforms, including Apple's macOS, iOS, watchOS, and tvOS, Google Search, the Android operating system, and FreeBSD." GCC ships [libstdc++](https://gcc.gnu.org/onlinedocs/libstdc++/), the default on most Linux distributions. - C++: [LWG issue 713](https://cplusplus.github.io/LWG/issue713), "sort() complexity is too lax," is the defect report that made the O(n log n) bound a worst-case requirement rather than an average one. libstdc++'s implementation is `__introsort_loop` in [stl_algo.h](https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=libstdc%2B%2B-v3/include/bits/stl_algo.h). libc++ only met the worst-case bound with [D113413](https://reviews.llvm.org/D113413), "Add introsort to avoid O(n^2) behavior," which shipped in LLVM 14. - The measurement: a million integers, `0..999999`, sorted and shuffled, comparisons counted through the comparator. Python 3.11.9 `sorted()` with `cmp_to_key`: 999,999 comparisons sorted, 18.6M random. GNU libstdc++ (GCC 16.1): 25.6M sorted, 24.4M random. LLVM libc++ (Apple clang 21, macOS): 2.0M sorted, 22.6M random. Wall clock without the counting wrapper, sorted input: Python 3.9 ms, libstdc++ 9.8 ms, libc++ 0.8 ms. The libc++ shortcut is the `__insertion_sort_incomplete` check after a "perfect partition" in [`__algorithm/sort.h`](https://github.com/llvm/llvm-project/blob/main/libcxx/include/__algorithm/sort.h). - Go: [Go 1.19 release notes](https://go.dev/doc/go1.19#sort): "The sorting algorithm has been rewritten to use pattern-defeating quicksort." The previous implementation is in [Go 1.18's sort.go](https://github.com/golang/go/blob/go1.18/src/sort/sort.go): quicksort "loosely following Bentley and McIlroy," with a heapsort fallback at a depth limit and insertion sort below 12 elements. - Rust: [Rust 1.81.0 announcement](https://blog.rust-lang.org/2024/09/05/Rust-1.81.0/), September 5, 2024. The algorithms are named in [PR #124032](https://github.com/rust-lang/rust/pull/124032): `slice::sort` to driftsort, `slice::sort_unstable` to ipnsort. - Ruby: [include/ruby/util.h](https://github.com/ruby/ruby/blob/master/include/ruby/util.h) defines `ruby_qsort` as `qsort_r` when the GNU version is available; [util.c](https://github.com/ruby/ruby/blob/master/util.c) wraps the BSD `qsort_r` or `qsort_s` otherwise, and only falls through to the bundled `mm.c` quicksort when none exists. [configure.ac](https://github.com/ruby/ruby/blob/master/configure.ac) does the detection. macOS's `qsort_r` is [Apple's copy of FreeBSD's qsort.c](https://github.com/apple-oss-distributions/Libc/blob/main/stdlib/FreeBSD/qsort.c), "from Bentley & McIlroy's 'Engineering a Sort Function'," with a heapsort fallback at a depth limit. The [Array#sort docs](https://docs.ruby-lang.org/en/master/Array.html#method-i-sort): "the order for a and b is indeterminate, and may be unstable." - Swift: [PR #19717](https://github.com/apple/swift/pull/19717), "Switch to a stable sort algorithm," merged November 7, 2018 and shipped in Swift 5. The review thread is where "not guaranteed stable" was chosen over a promise, since committing to stability would need a Swift Evolution proposal. - PHP: [RFC: Make sorting stable](https://wiki.php.net/rfc/stable_sorting), Nikita Popov, May 2020, accepted 45 to 0 for PHP 8.0. Stability comes from using original position as a fallback criterion; small arrays (up to 16 elements) were already unaffected. - C#: [Array.Sort documentation](https://learn.microsoft.com/en-us/dotnet/api/system.array.sort): introsort, insertion sort at 16 or fewer elements, heapsort past a depth limit, "performs an unstable sort." Notes to Callers: ".NET Framework 4 and earlier versions used only the Quicksort algorithm."
JavaScript engines - Internet Explorer's stable sort: [Mozilla bug 224128, comment 4](https://bugzilla.mozilla.org/show_bug.cgi?id=224128#c4), Mike Shaver, October 2003: "More compelling even than that quote is the fact that IE's sort is stable." - SpiderMonkey quicksort to heapsort: [Mozilla bug 99120](https://bugzilla.mozilla.org/show_bug.cgi?id=99120), filed September 10, 2001. The patch landed as jsarray.c revision 3.33 on March 13, 2002, logged in comment 61 as "switch from QuickSort to heap-sort." Brendan Eich's later summary is [bug 224128, comment 8](https://bugzilla.mozilla.org/show_bug.cgi?id=224128#c8): "we switched to heap sort from (also unstable) QuickSort because of 'benchmark-itis'." - SpiderMonkey heapsort to merge sort: [Mozilla bug 224128](https://bugzilla.mozilla.org/show_bug.cgi?id=224128), filed October 29, 2003; Nicholas Allen's patch posted November 2003; landed on trunk October 5, 2006 as jsarray.c revision 3.98; shipped in Firefox 3 per comment 63. Today's implementation is [js/src/ds/Sort.h](https://searchfox.org/firefox-main/source/js/src/ds/Sort.h). - JavaScriptCore: the AVL tree arrived in [WebKit r33967](https://commits.webkit.org/26483@main), May 21, 2008, Alexey Proskuryakov, fixing a people.com crash caused by `sort(function() { return 0.5 - Math.random(); })`. The sort modes the 2015 rewrite deleted are all visible in [the removed code](https://github.com/WebKit/WebKit/commit/d9d3a5d8f416551b9b238bca1cf1e445ab05ec3a): `mergesort` for string comparisons, `qsort` for numeric ones, `AVLTree` for custom comparators, and a "Min" sort in `performSlowSort` for non-array objects. The JavaScript rewrite is [WebKit r183570](https://commits.webkit.org/162412@main), April 29, 2015, Geoffrey Garen, "It shouldn't take 1846 lines of code and 5 FIXMEs to sort an array." The "fairly naive" line is [WebKit bug 239267](https://bugs.webkit.org/show_bug.cgi?id=239267), April 12, 2022, Robin Morisset. Bun [runs on JavaScriptCore](https://bun.sh/docs). - V8: ["Getting things sorted in V8"](https://v8.dev/blog/array-sort), Simon Zünd, September 28, 2018: "a Quicksort with an Insertion Sort fall-back for shorter arrays," Timsort "available starting with V8 v7.0 and Chrome 70," written in Torque, and the stable-sort request "among the oldest tickets in V8's bug tracker." The 10-element threshold is in [V8 6.9's array.js](https://chromium.googlesource.com/v8/v8/+/6.9.427/src/js/array.js#647): "For short (length <= 10) arrays, insertion sort is used for efficiency." Chakra's 512-element threshold is in [ChakraCore 1.11's JavascriptArray.cpp](https://github.com/chakra-core/ChakraCore/blob/v1.11.0/lib/Runtime/Library/JavascriptArray.cpp#L6640-L6647): "for arrays of more than 512 elements." [Node 11.0.0](https://nodejs.org/en/blog/release/v11.0.0) shipped V8 7.0 on October 23, 2018. - Chakra: [ChakraCore PR #5724](https://github.com/chakra-core/ChakraCore/pull/5724), "Implement stable MergeSort for Array.prototype.sort," merged November 1, 2018. - Hermes: ["Using Hermes's Quicksort to run Doom"](https://engineering.fb.com/2022/07/20/security/hermes-quicksort-to-run-doom/), Luigi Coniglio, Meta, July 20, 2022. Reported through the bug bounty in August 2020, within six days of the change, before any public release. - QuickJS: `rqsort` lives in [cutils.c](https://github.com/bellard/quickjs/blob/master/cutils.c): median-of-three pivot, three-way partition, insertion sort threshold, heapsort fallback. The stability shim is in [quickjs.c](https://github.com/bellard/quickjs/blob/master/quickjs.c), under the comment "make sort stable: compare array offsets." - Rhino: [commit aeaf4c0](https://github.com/mozilla/rhino/commit/aeaf4c095c4f8cebcc43a13242102e5d78da05e9), January 31, 2002, Igor Bukanov, "Use heapsort instead of qsort for Array.sort to follow JS." The switch to Java's `Arrays.sort` is [Mozilla bug 399348](https://bugzilla.mozilla.org/show_bug.cgi?id=399348), 2007. - The spec: [ECMAScript 5.1, section 15.4.4.11](https://262.ecma-international.org/5.1/#sec-15.4.4.11): "The sort is not necessarily stable." The change is [tc39/ecma262 PR #1340](https://github.com/tc39/ecma262/pull/1340), "Normative: Make Array.prototype.sort stable," Mathias Bynens, merged January 29, 2019, in time for ES2019. The current spec's [SortIndexedProperties](https://tc39.es/ecma262/multipage/indexed-collections.html#sec-sortindexedproperties) sorts "using an implementation-defined sequence of calls to SortCompare," which is why comparator side effects still differ by engine. The default string comparison is [documented on MDN](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort).
Engines and runtimes - [JScript](https://en.wikipedia.org/wiki/JScript), Microsoft's engine in [Internet Explorer 4](https://en.wikipedia.org/wiki/Internet_Explorer_4) through 8. - [SpiderMonkey](https://en.wikipedia.org/wiki/SpiderMonkey), Brendan Eich's original engine, shipped in [Netscape Communicator](https://en.wikipedia.org/wiki/Netscape_Communicator) (Netscape 4) and every Firefox since, including [Firefox 3](https://en.wikipedia.org/wiki/Firefox_3). - [Rhino](https://en.wikipedia.org/wiki/Rhino_(JavaScript_engine)), Mozilla's JavaScript on the JVM, from 1999. - [JavaScriptCore](https://en.wikipedia.org/wiki/JavaScriptCore), Apple's engine in [Safari](https://en.wikipedia.org/wiki/Safari_(web_browser)) and in [Bun](https://en.wikipedia.org/wiki/Bun_(software)). - [V8](https://en.wikipedia.org/wiki/V8_(JavaScript_engine)), Google's engine in [Chrome](https://en.wikipedia.org/wiki/Google_Chrome), [Node.js](https://en.wikipedia.org/wiki/Node.js), [Deno](https://en.wikipedia.org/wiki/Deno_(software)), [Electron](https://en.wikipedia.org/wiki/Electron_(software_framework)) and [Cloudflare Workers](https://developers.cloudflare.com/workers/). [Torque](https://v8.dev/docs/torque) is V8's internal language for writing builtins. - [Chakra](https://en.wikipedia.org/wiki/Chakra_(JavaScript_engine)), Microsoft's engine in [Internet Explorer 9](https://en.wikipedia.org/wiki/Internet_Explorer_9) through the original, pre-Chromium [Microsoft Edge](https://en.wikipedia.org/wiki/Microsoft_Edge). - [Hermes](https://hermesengine.dev/), Meta's engine for [React Native](https://en.wikipedia.org/wiki/React_Native). - [QuickJS](https://bellard.org/quickjs/), Fabrice Bellard's embeddable engine. [Duktape](https://duktape.org/), the other common embedded engine, is left off the list because I couldn't confirm which algorithm it uses. - [ECMAScript version history](https://en.wikipedia.org/wiki/ECMAScript_version_history), for ES3 (1999), ES5.1 (2011) and ES2019.