Skip to content

Instantly share code, notes, and snippets.

@bogoreh
Last active March 2, 2021 14:38
Show Gist options
  • Select an option

  • Save bogoreh/1b374ae9440c9f9e08a48e2623985560 to your computer and use it in GitHub Desktop.

Select an option

Save bogoreh/1b374ae9440c9f9e08a48e2623985560 to your computer and use it in GitHub Desktop.
// Takes in an array that has two sorted subarrays,
// from [p..q] and [q+1..r], and merges the array
var merge = function(array, p, q, r) {
// This code has been purposefully obfuscated,
// as you'll write it yourself in next challenge.
var a=[],b=[],c=p,d,e;for(d=0;c<=q;d++,c++){a[d]=array[c];}for(e=0;c<=r;e++,c++){b[e]=array[c];}c=p;for(e=d=0;d<a.length&&e<b.length;){if(a[d]<b[e]){array[c]=a[d];d++;} else {array[c]=b[e]; e++;}c++; }for(;d<a.length;){array[c]=a[d];d++;c++;}for(;e<b.length;){array[c]=b[e];e++;c++;}
};
// Takes in an array and recursively merge sorts it
var mergeSort = function(array, p, r) {
if (p < r){
var q = floor((p+r)/2);
mergeSort(array, p, q);
mergeSort(array, q+1, r);
merge(array, p, q, r);
}
};
var array = [14, 7, 3, 12, 9, 11, 6, 2];
mergeSort(array, 0, array.length-1);
println("Array after sorting: " + array);
Program.assertEqual(array, [2, 3, 6, 7, 9, 11, 12, 14]);
var array2 = [0, 14, -10, 8, 12, 6, 7, 40];
mergeSort(array2, 0, array2.length-1);
Program.assertEqual(array2, [-10, 0, 6, 7, 8, 12, 14, 40]);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment