Как улучшить производительность при слиянии, сортировка массивов javascript

Question

У меня есть два массива. Один сортируется, другой - нет.

Сортированный массив довольно большой, допустим, 90 000 записей. Второй массив будет коротким - в настоящее время не более 401.

Проблема в том, что я загружаю файл и читаю этот файл для определения значений для ввода короткого массива, когда я закончил с этим файлом короткий массив должен быть объединен с отсортированным массивом и сериализован на диск. Я делаю слияние и то, как можно было бы ожидать:

var hashes = [ 
"M2E0Mzk3YmItOWUzMC00ZmMwLWFhZDQtYTA0NTk0YWIwYjhjXw==mtg0mtq3nze2nw", 
"M2ExZjNmNDktODdhOS00ODJiLTg2NzQtM2NiODQ1Njc1ZmYzXw==lte0mzg2otgxmdk", 
"M2EzNTExM2UtY2JmYS00ZjAzLTgwZmMtMjg4ZDJkZjA5YzJjXw==mtcxmjqxmdc1mq", 
"M2EzZjkzZDQtODUwYS00ZjlkLTg3ZmQtZjliNTFjZmYxNjVhXw==mjgzodu3nji3" ]; 

var append_to_hashes = [ 
"M2E2NGZjNWEtMzkwYy00YzE4LTkzM2EtNDVmNjE1MjE2ZDViXw==ltcxmzk1otawng", 
"M2ExZjE2NGItNzUwZi00YTU4LWI3OGMtZDVkNDA2YWE2MzRmXw==ltq3odgznja2op", 
"M2ExZjE2NGItNzUwZi00YTU4LWI3OGMtZDVkNDA2YWE2MzRmXw==ltq3odgznja2oa"]; 

if(append_to_hashes.length > 0){ 
    hashes = hashes.concat(append_to_hashes); 
    hashes = hashes.sort(); 
} 

Но мне интересно, если есть более производительный способ объединения и сортировки массивов.

Answer 1

Вы можете отсортировать меньший массив, а затем вставьте каждый элемент в нужном месте:

var big = [...]; // Big sorted array 
var small = [...]; // Small unsorted array 

small.sort(); 

for(let i = 0; i < big.length && small.length > 0; i++) { 
    if(big[i].localeCompare(small[0]) > 0) { 
     big.splice(i, 0, small.shift()); 
    } 
}