He buscado en muchos otros recursos pero no he podido encontrar una respuesta de calidad a esta pregunta.
Los objetos de JavaScript ordenan sus claves enteras en orden ascendente, no en orden de inserción.
const lookup = {}
lookup['1'] = 1
lookup['3'] = 3
lookup['2'] = 2
console.log(Object.keys(lookup)) -> ['1', '2', '3']
Eso es simple. Pero, ¿cuál es la gran notación O de ese proceso de clasificación interna? Algún algoritmo de clasificación debe estar ocurriendo debajo del capó para clasificar esas claves a medida que se insertan, pero no puedo averiguar cuál es.
Array.sort() con una longitud de <= 10 es Ordenación por inserción y Array.sort() con una longitud > 10 es Ordenación rápida
Pero Array.sort() está reordenando las claves de un objeto en función de la clasificación de sus valores.
¿Cómo JavaScript debajo del capó ordena sus claves al insertarlas?
(Desarrollador V8 aquí.)
Depende, como tantas veces.
Si las propiedades con clave entera son lo suficientemente densas, el objeto usará una matriz debajo del capó para almacenarlas. En comparación con los algoritmos de clasificación, sería lo más parecido a la "clasificación radix", con la notable diferencia de que no hay un paso de clasificación explícito: el orden de clasificación surge como un efecto secundario "gratuito" de la forma en que se almacenan los elementos. Cuando se ejecuta lookup[2] = ... , el valor se escribirá en la ranura respectiva de la matriz. Si la matriz no es lo suficientemente grande, se asigna una nueva matriz y se copian las entradas existentes; dado que eso no sucede con demasiada frecuencia, el costo de una inserción sigue siendo "O (1) amortizado". Al obtener la lista de propiedades con clave entera, la matriz ya está ordenada.
Si las propiedades con clave entera son demasiado escasas, el objeto pasará a usar un diccionario como almacén de respaldo. Los diccionarios basados en hash almacenan las entradas en su propio orden "aleatorio", por lo que, en ese caso Object.keys() y operaciones similares tienen que realizar un paso de clasificación explícito. Parece que actualmente confiamos en std::sort de C++ para eso, pero eso es un detalle de implementación que podría cambiar (no solo del lado de V8, también cómo se implementa std::sort depende de la biblioteca estándar a la que está vinculado V8 contra).
Array.sort() con una longitud de <= 10 es Ordenación por inserción y Array.sort() con una longitud > 10 es Ordenación rápida
No, no más. Nos cambiamos a TimSort en 2018.