Created
February 5, 2019 13:29
-
-
Save ungarson/80d32cdc28aa6631f91f40414431249e to your computer and use it in GitHub Desktop.
Merge sort in javascript
This file contains hidden or 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
/** | |
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