Array.prototype.sort

A polyfill is code that adds a standard feature to an environment that doesn't have it yet, such as Promise.any or Array.prototype.flat in an older browser. It's written in plain JavaScript that the old environment can already run, and it follows the specification, the document that defines how the feature behaves, as closely as it can. Code written for new browsers then works in old ones too. The name comes from Polyfilla, a paste for filling cracks in walls: a polyfill fills the gaps in a browser.

A real polyfill checks for the feature first, as in if (!Promise.any), and defines it only when it's missing, so a browser that has the built-in keeps its own version:

if (!Array.prototype.flat) {
  Array.prototype.flat = function flat(depth) {
    // the steps the specification lists, written in plain JavaScript
  };
}

Every array gets its methods from one shared object, Array.prototype, and every function from Function.prototype. So a method added there appears on every array or function in the program, even ones created before it was added, and inside it this is the array or function it was called on. Careful polyfills add it with Object.defineProperty rather than = as above, so that, like the built-ins, it isn't enumerable and doesn't show up in a for...in loop.

When an interviewer asks you to write a polyfill, they mean: reproduce a built-in's behaviour yourself, without calling it. It shows you know exactly what the built-in does, beyond its everyday use. The details are the point, because code written against the standard relies on them too:

These tasks give your version its own name, such as Array.prototype.myMap, Object.myCreate, or JSON.myStringify, or make it a stand-alone function, such as promiseAll(iterable) or objectIs(a, b). Replacing the real method would change it for every other piece of code on the page, and leave you no built-in to compare yours with.

In production you rarely write polyfills by hand: libraries such as core-js provide them, and Babel can add the ones your target browsers need. A polyfill can only add missing objects, functions, and methods. New syntax, such as ?. or class, can't be added that way: a compiler has to rewrite it as older syntax, which is called transpiling.

An array's length counts slots, and a slot can be empty: no element at all, not even undefined. That empty slot is called a hole, and an array with holes is called sparse. Reading a hole gives undefined, the value you get for any property that doesn't exist, so it looks like an element holding undefined. Object.keys, which lists the indexes an array really has, tells the two apart:

const withHole = [1, , 3]; // nothing between the commas
const withUndefined = [1, undefined, 3];
 
withHole.length;      // 3
withUndefined.length; // 3
withHole[1];          // undefined
withUndefined[1];     // undefined
Object.keys(withHole);      // ["0", "2"]: there's no element at index 1
Object.keys(withUndefined); // ["0", "1", "2"]: there is one, and its value is undefined

Holes appear in a few ways:

Consoles mark holes so you can spot them: Chrome shows [1, , 3] as [1, empty, 3], and Node as [ 1, <1 empty item>, 3 ].

Built-in methods don't agree on what to do with a hole: some skip it, some keep it in their result, and some read it as undefined, or write null in JSON. That's why every task that rebuilds one of them says exactly what to do with holes. Here's [1, , 3] going through a few:

A sort is stable when items that compare as equal keep the order they had before the sort. With a compare function, equal means it returns 0 for the pair: sorted by age, two people of the same age are equal, even though their names differ. A stable sort leaves them in the order they came in. An unstable sort may put them either way round, and which way can depend on the engine or on how long the array is.

Picture a queue at a ticket office that lets members go first. A fair clerk moves the members to the front, but keeps the members in the order they arrived, and everyone else too. That's a stable sort. An unfair one also gets the members to the front, but mixes up who was standing where.

const people = [
  { name: "Ada", age: 30 },
  { name: "Bo", age: 25 },
  { name: "Cy", age: 30 },
  { name: "Di", age: 25 },
];
 
people.toSorted((a, b) => a.age - b.age).map((person) => person.name);
// ["Bo", "Di", "Ada", "Cy"]: Bo stays ahead of Di, and Ada ahead of Cy

Both results are sorted by age, and the compare function can't tell them apart. Only the stable one is predictable: you know where Bo and Di will be before you sort.

In a UI, stability is what lets one sort build on another. The list above started in name order, and after the stable sort by age, the people of each age are still in name order. A sortable table works the same way: sort it by name, then click the Age header, and people of the same age stay in name order. With an unstable sort, each click could scramble the rows that tie, even when nothing in the data changed.

Since ES2019, the specification requires Array.prototype.sort to be stable, so every current engine sorts stably, and toSorted, added in ES2023, is stable too. Before that, engines could choose: until Chrome 70, in 2018, Chrome sorted arrays of more than 10 elements with an unstable sort. A polyfill, or any sort you write yourself, has to be stable on purpose.

Sorting algorithms differ here. Merge sort and insertion sort are stable. Quicksort, selection sort, and heap sort, in their usual forms, are not: they can move an item past one it's equal to. V8, the engine in Chrome and Node, sorts with TimSort, a stable mix of merge sort and insertion sort.