You are given two arrays of integers, sorted in ascending order. Your task is to write a function that merges the two arrays, and output a merged array that is also sorted. But there's the catch! The Array.prototype.sort() function is not available!
For example, given the following two arrays:
[0, 3, 6, 13, 45]
[-1, 45, 330, 553]
Your function should return:
[-1, 0, 3, 6, 13, 45, 45, 330, 553]
Note that there may be duplicates. It's fine to leave them in there.
function mergeArrays(arrA, arrB) {
const output = [];
const arrAClone = [...arrA];
const arrBClone = [...arrB];
let nextSmallestA = arrAClone.shift();
let nextSmallestB = arrBClone.shift();
while (nextSmallestA !== undefined || nextSmallestB !== undefined) {
if (nextSmallestA === undefined || nextSmallestB < nextSmallestA) {
output.push(nextSmallestB);
nextSmallestB = arrBClone.shift();
} else {
output.push(nextSmallestA);
nextSmallestA = arrAClone.shift();
}
}
return output;
}// If the failure output for deep equality is truncated, `chai.config.truncateThreshold` can be adjusted.
const assert = require("assert");
describe("mergeArray", function() {
it("should work for 2 empty arrays", function() {
const arr1 = [];
const arr2 = [];
const expected = [];
const actual = mergeArrays(arr1, arr2);
assert.deepStrictEqual(actual, expected);
});
it("should work with a single empty array", function() {
const arr1 = [1,3,5,7,9,11,13,15,17,19,200];
const arr2 = [];
const expected = [1,3,5,7,9,11,13,15,17,19,200];
const actual = mergeArrays(arr1, arr2);
assert.deepStrictEqual(actual, expected);
});
it("should work with large numbers", function() {
const arr1 = [64649367165265, 274632412695799, 412877423124429, 516230628864647, 538837081813693, 746373629824209, 1692897751449627, 2270037413537007, 2733584891633993, 2812411720528947, 2882676970678137, 2903411384421675, 2958418807276103, 3130000929603865, 3175980736717465, 3614311465231655, 3996463578205695, 4103082738409165, 4258621578191541, 4418610303201609, 4647855513194407, 4685348960324559, 4808920381357755, 5183451753845617, 5248837872019479, 5459393081841211, 6169730898746597, 6569116706507233, 6603729845179117, 7155136605307029, 7212160056015967, 7244553210477423, 7384589786348845, 7713430447934781, 8114895595811233, 8209510986022041, 8398715614919241, 8563902159010211, 8691058183717011, 8962445733616225];
const arr2 = [163457591720831, 196860880460605, 668872604533663, 681475781382441, 739991228922867, 1204232377264725, 1402567083052239, 1418358979840983, 1875285439667131, 2112478608256379, 2362707116240501, 2480247716891123, 2815699197032227, 2946539963432449, 2978823594913687, 3298444539285921, 3664268267691413, 4277457216782315, 4316531169004027, 4567307451346087, 4655426574120211, 4696413724870613, 4831259468359653, 5052243723913683, 5076825973761899, 5313627140975321, 5549643481155739, 5763038910068197, 5863617689275713, 6100078677408673, 6182322012227663, 6673442111678693, 6677992076967503, 6765194736438189, 6794436664762403, 7138122320940275, 7407652791154167, 7650254427397051, 8784125927428599, 8794961983529061];
const expected = [64649367165265, 163457591720831, 196860880460605, 274632412695799, 412877423124429, 516230628864647, 538837081813693, 668872604533663, 681475781382441, 739991228922867, 746373629824209, 1204232377264725, 1402567083052239, 1418358979840983, 1692897751449627, 1875285439667131, 2112478608256379, 2270037413537007, 2362707116240501, 2480247716891123, 2733584891633993, 2812411720528947, 2815699197032227, 2882676970678137, 2903411384421675, 2946539963432449, 2958418807276103, 2978823594913687, 3130000929603865, 3175980736717465, 3298444539285921, 3614311465231655, 3664268267691413, 3996463578205695, 4103082738409165, 4258621578191541, 4277457216782315, 4316531169004027, 4418610303201609, 4567307451346087, 4647855513194407, 4655426574120211, 4685348960324559, 4696413724870613, 4808920381357755, 4831259468359653, 5052243723913683, 5076825973761899, 5183451753845617, 5248837872019479, 5313627140975321, 5459393081841211, 5549643481155739, 5763038910068197, 5863617689275713, 6100078677408673, 6169730898746597, 6182322012227663, 6569116706507233, 6603729845179117, 6673442111678693, 6677992076967503, 6765194736438189, 6794436664762403, 7138122320940275, 7155136605307029, 7212160056015967, 7244553210477423, 7384589786348845, 7407652791154167, 7650254427397051, 7713430447934781, 8114895595811233, 8209510986022041, 8398715614919241, 8563902159010211, 8691058183717011, 8784125927428599, 8794961983529061, 8962445733616225];
const actual = mergeArrays(arr1, arr2);
assert.deepStrictEqual(actual, expected);
});
it("should work with negative numbers", function() {
const arr1 = [-4627886, -4519642, -4297468, -3595491, -3205849, -3099984, -2661963, -2191758, -1832781, -1477357, -1471131, -1392509, -455864, 250084, 1071449, 1103428, 1305440, 1425801, 1452987, 1532745, 1820483, 1840962, 2148348, 2527057, 2706849, 2812677, 2835553, 2947423, 3258963, 3343546, 3493747, 3549879, 4084746, 4159368, 4323454, 4500321, 4642668, 4726588, 4913852, 4978575];
const arr2 = [-1436270, -1334241, -694068, -244520, 1285751, 1459606, 1914385, 2306127, 6078989, 6238068, 6361720, 8166625, 8603728, 8767531, 8886489, 9376132, 10396281, 12030028, 15631727, 17886989, 19258356, 19806234, 24055975, 24357484, 26714565, 26764202, 26854242, 27389146, 28432253, 28734874, 31107482, 31394025, 32185014, 32211940, 33730728, 35244675, 35505202, 35540727, 36742659, 38872319];
const expected = [-4627886, -4519642, -4297468, -3595491, -3205849, -3099984, -2661963, -2191758, -1832781, -1477357, -1471131, -1436270, -1392509, -1334241, -694068, -455864, -244520, 250084, 1071449, 1103428, 1285751, 1305440, 1425801, 1452987, 1459606, 1532745, 1820483, 1840962, 1914385, 2148348, 2306127, 2527057, 2706849, 2812677, 2835553, 2947423, 3258963, 3343546, 3493747, 3549879, 4084746, 4159368, 4323454, 4500321, 4642668, 4726588, 4913852, 4978575, 6078989, 6238068, 6361720, 8166625, 8603728, 8767531, 8886489, 9376132, 10396281, 12030028, 15631727, 17886989, 19258356, 19806234, 24055975, 24357484, 26714565, 26764202, 26854242, 27389146, 28432253, 28734874, 31107482, 31394025, 32185014, 32211940, 33730728, 35244675, 35505202, 35540727, 36742659, 38872319];
const actual = mergeArrays(arr1, arr2);
assert.deepStrictEqual(actual, expected);
});
it("should work with zeros", function() {
const arr1 = [-4627886, -4519642, -4297468, -3595491, -3205849, -3099984, -2661963, -2191758, -1832781, -1477357, -1471131, -1392509, -455864, 0, 250084, 1071449, 1103428, 1305440, 1425801, 1452987, 1532745, 1820483, 1840962, 2148348, 2527057, 2706849, 2812677, 2835553, 2947423, 3258963, 3343546, 3493747, 3549879, 4084746, 4159368, 4323454, 4500321, 4642668, 4726588, 4913852, 4978575];
const arr2 = [-1436270, -1334241, -694068, -244520, 0, 1285751, 1459606, 1914385, 2306127, 6078989, 6238068, 6361720, 8166625, 8603728, 8767531, 8886489, 9376132, 10396281, 12030028, 15631727, 17886989, 19258356, 19806234, 24055975, 24357484, 26714565, 26764202, 26854242, 27389146, 28432253, 28734874, 31107482, 31394025, 32185014, 32211940, 33730728, 35244675, 35505202, 35540727, 36742659, 38872319];
const expected = [-4627886, -4519642, -4297468, -3595491, -3205849, -3099984, -2661963, -2191758, -1832781, -1477357, -1471131, -1436270, -1392509, -1334241, -694068, -455864, -244520, 0, 0, 250084, 1071449, 1103428, 1285751, 1305440, 1425801, 1452987, 1459606, 1532745, 1820483, 1840962, 1914385, 2148348, 2306127, 2527057, 2706849, 2812677, 2835553, 2947423, 3258963, 3343546, 3493747, 3549879, 4084746, 4159368, 4323454, 4500321, 4642668, 4726588, 4913852, 4978575, 6078989, 6238068, 6361720, 8166625, 8603728, 8767531, 8886489, 9376132, 10396281, 12030028, 15631727, 17886989, 19258356, 19806234, 24055975, 24357484, 26714565, 26764202, 26854242, 27389146, 28432253, 28734874, 31107482, 31394025, 32185014, 32211940, 33730728, 35244675, 35505202, 35540727, 36742659, 38872319];
const actual = mergeArrays(arr1, arr2);
assert.deepStrictEqual(actual, expected);
});
});