I'm doing a course on Khan Academy on Algorithms.
I usually try to figure out the examples by myself but this time I am really not getting it. The exercise is at: Khan Academy Merge Sort Exercise.
So I'm asking a kind person to please resolve this exercise for me, because I'm stuck and it is the first time that I can't implement something. I'm sure that I will understand the algorithm (I think I do, but it gives me errors on implementing, so apparently I'm not understanding) after seem the resolution.
Here is the code that I have done so far:
// 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(r > 1) {
var q = Math.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];
console.log(''+array);
mergeSort(array, 0, array.length-1);
console.log("Array after sorting: " + array);
// 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(r > 1) {
var q = Math.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];
console.log(''+array);
mergeSort(array, 0, array.length-1);
console.log("Array after sorting: " + array);
It has something to do with the if
condition
what the if condition achieves is to check that the r
that is end of array is greater that p
start of the array.
I'm not sure what r > 1
is trying to do. hence it doesn't get satisfied and executes recursively untill it runs out of stack space
// 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 (r > p) {
var q = Math.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];
console.log('' + array);
mergeSort(array, 0, array.length - 1);
console.log("Array after sorting: " + array);