Last active
March 2, 2021 14:38
-
-
Save bogoreh/1b374ae9440c9f9e08a48e2623985560 to your computer and use it in GitHub Desktop.
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
| // 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