Created
April 5, 2016 13:57
-
-
Save rafaelquintanilha/665aa63718bc3b7fbee9c33686f98188 to your computer and use it in GitHub Desktop.
Merge two already sorted arrays
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function merge(arr1, arr2) { | |
var result = []; // Array where elements will be added | |
var i1 = 0; // Index for arr1 | |
var i2 = 0; // Index for arr2 | |
// Iterate over arrays until reach the end of one of them | |
while ( i1 < arr1.length && i2 < arr2.length ) { | |
arr1[i1] < arr2[i2] ? result.push(arr1[i1++]) : result.push(arr2[i2++]) // Push the smallest and increment | |
} | |
// Return result concat'ed with the remaining items from array that didn't reach the end | |
return result.concat(arr1.slice(i1)).concat(arr2.slice(i2)); | |
} | |
// Test some input | |
var arr1 = [2, 3, 5, 5, 9, 10, 13]; | |
var arr2 = [6, 7, 7, 7, 9, 10, 10, 12, 15]; | |
var merged = merge(arr1, arr2); | |
for ( i = 0; i < merged.length; i++ ) console.log(merged[i]); | |
// merged = [2, 3, 5, 5, 6, 7, 7, 7, 9, 9, 10, 10, 10, 12, 13, 15] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Complexity: O(n)