Skip to content

Instantly share code, notes, and snippets.

@jinwolf
Last active December 31, 2015 06:34
Show Gist options
  • Save jinwolf/d811bd2735a61bbcd587 to your computer and use it in GitHub Desktop.
Save jinwolf/d811bd2735a61bbcd587 to your computer and use it in GitHub Desktop.
Merge sorted arrays into one (JavaScript)
var sorted_lists = [
[3, 4, 6, 10, 11, 15],
[1, 5, 8, 12, 14, 19],
[2, 7, 9, 13, 16, 17, 18],
[20, 22, 23, 25]
];
function mergeSortedArrays(sortedLists) {
var pointers = new Array(sortedLists.length);
for (var i = 0; i < pointers.length; i++) {
pointers[i] = 0;
}
var mergedPointer = 0;
var totalLength = 0;
sortedLists.forEach(function(item) {
totalLength += item.length;
});
var merged = new Array(totalLength);
while(mergedPointer < totalLength) {
var args = [];
for (var i =0; i < sortedLists.length; i++) {
args.push(sortedLists[i][pointers[i]]);
}
var minIndex = getMinIndex(args);
merged[mergedPointer] = sortedLists[minIndex][pointers[minIndex]];
pointers[minIndex]++;
mergedPointer++;
}
return merged;
function getMinIndex(list) {
var min = list[0];
var minIndex = 0;
for(var i = 1; i < list.length; i++) {
if (list[i] && (!min || list[i] < min)) {
min = list[i];
minIndex = i;
}
}
return minIndex;
}
}
console.log(mergeSortedArrays(sorted_lists));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment