Skip to content

Instantly share code, notes, and snippets.

@ungarson
Created February 5, 2019 13:29
Show Gist options
  • Save ungarson/80d32cdc28aa6631f91f40414431249e to your computer and use it in GitHub Desktop.
Save ungarson/80d32cdc28aa6631f91f40414431249e to your computer and use it in GitHub Desktop.
Merge sort in javascript
/**
Imagine we have [1, 2] and [3,4]
So using merge_union we will concatenate these arrays and sort them right
merge_union([2,1], [3,4]) ---> [1,2,3,4]
merge_union([2,3,4,5], [-5,-3,100]) ---> [-5, -3, 2, 3, 4, 5, 100]
**/
function merge_union(arr1, arr2) {
let result = [];
// i is for arr1 and j is for arr2
let i = 0; let j = 0;
/**
if we are done with one of the arrays, another array could be not empty
so we use stopped variable to fill result with this "another not empty" array
And countOut variable is how much elements we've left, so we fill result array with this amount of elements
**/
let stopped, countOut;
/**
set_vars is for assigning a value to variables above
**/
function set_vars(stop) {
if (stop === 0) {
countOut = arr2.length - j;
j = arr2.length;
stopped = 0;
} else {
countOut = arr1.length - i;
i = arr2.length;
stopped = 1;
}
}
for (i; i < arr1.length;) {
for (j; j < arr2.length;) {
if (arr1[i] < arr2[j]) { // if you want another order, you need to change ">" to "<" and visa versa
result.push(arr1[i]);
i += 1;
// we might be done with arr1 array but arr2 could be not empty
if (i == arr1.length) set_vars(0);
} else if (arr1[i] == arr2[j]) {
result.push(arr1[i], arr1[i]);
i += 1, j += 1;
if (i == arr1.length && j == arr2.length) break;
// we might be done with arr1 (arr2) array but arr2 (arr1) could be not empty
if (i == arr1.length) set_vars(0);
else if (j == arr2.length) set_vars(1);
} else {
result.push(arr2[j]);
j += 1;
// we might be done with arr2 array but arr1 could be not empty
if (j == arr2.length) set_vars(1);
}
}
}
if (stopped === undefined) return result; // in case we took every element from both arrays, so everything s ok
else if (stopped === 0) { // in case we have stopped at the arr1
result = result.concat(arr2.slice(-countOut));
return result;
} else { // in case we have stopped at the arr2
result = result.concat(arr1.slice(-countOut));
return result;
}
}
function merge_sort(arr) {
if (arr.length <= 1) return arr;
return merge_union(merge_sort(arr.slice(0, Math.floor(arr.length/2))),merge_sort(arr.slice(-Math.ceil(arr.length/2))));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment