JavaScript Objects and Sorted Integer Keys under the hood

Question

I have searched a bunch of other resources but have not been able to find a quality answer to this question.

JavaScript objects sort their integer keys in ascending order, not insertion order.

const lookup = {}

lookup['1'] = 1
lookup['3'] = 3
lookup['2'] = 2

console.log(Object.keys(lookup)) -> ['1', '2', '3']

That much is simple. But what is the big O notation of that internal sorting process? Some sort algorithm must be happening under the hood to sort those keys as they are inserted but I can't find out which one it is.

Array.sort() with a length of <= 10 is Insertion Sort and Array.sort() with a length > 10 is Quick Sort

But Array.sort() is reordering an object's keys based off of the sorting of its values.

How does JavaScript under the hood sort its keys on insertion?

There's an array under the hood, and numeric keys are simply indexes into it. Access time is O(1) — Barmar, Sep 21 '22 at 17:46
possibly related answer: https://stackoverflow.com/a/38218582/5334486 — GrafiCode, Sep 21 '22 at 17:48
There's no sorting going on, it's just showing the indexes in numeric order. That's WHY numeric keys are shown in that order, rather than insertion order. — Barmar, Sep 21 '22 at 17:48

jmrk · Accepted Answer · 2022-09-22T11:25:53.570

(V8 developer here.)

It depends, as so often.

If the integer-keyed properties are sufficiently dense, the object will use an array under the hood to store them. Compared to sorting algorithms, that'd be closest to "radix sort", with the notable difference that there is no explicit sorting step: the sort order arises as a "free" side effect of the way elements are stored. When lookup[2] = ... is executed, the value will be written into the respective slot of the array. If the array isn't big enough, a new array is allocated, and existing entries are copied over; since that doesn't happen too often, the cost of an insertion is still "O(1) amortized". When getting the list of integer-keyed properties, then the array is already in sorted order.

If the integer-keyed properties are too sparse, the object will switch to using a dictionary as the backing store. Hash-based dictionaries store entries in their own "random" order, so in that case Object.keys() and similar operations actually have to perform an explicit sorting step. Looks like we're currently relying on C++'s std::sort for that, but that's very much an implementation detail that could change (not just on V8's side, also how std::sort is implemented depends on the standard library that V8 is linked against).

Array.sort() with a length of <= 10 is Insertion Sort and Array.sort() with a length > 10 is Quick Sort

No, not any more. We switched to TimSort in 2018.

JavaScript Objects and Sorted Integer Keys under the hood

1 Answers1