I am trying to observe my recursive merge sort slicing the arrays by each step.
function mergeSort(arr) {
if(arr.length === 1) return arr;
const mid = Math.floor(arr.length / 2);
const leftArray = arr.slice(0, mid);
const rightArray = arr.slice(mid, arr.length);
console.log(leftArray, rightArray)
return merge(mergeSort(leftArray), mergeSort(rightArray));
}
function merge(leftArray, rightArray) {
const sortedArray = [];
while(leftArray.length > 0 && rightArray.length > 0) {
if(leftArray[0] < rightArray[0]) {
sortedArray.push(leftArray[0]);
leftArray.shift();
} else {
sortedArray.push(rightArray[0]);
rightArray.shift();
}
}
return sortedArray.concat(leftArray).concat(rightArray);
}
If you see the code above, I am logging leftArray and rightArray. But that logs every step at once as soon as I run the code. In order to control the code execution, I made my mergeSort function into a generator function so that whenever I run .next() I could see the next slice.
function * mergeSort(arr) {
if(arr.length === 1) return arr;
const mid = Math.floor(arr.length / 2);
const leftArray = arr.slice(0, mid);
const rightArray = arr.slice(mid, arr.length);
yield console.log(leftArray, rightArray);
return merge(mergeSort(leftArray), mergeSort(rightArray));
}
function merge(leftArray, rightArray) {
const sortedArray = [];
while(leftArray.length > 0 && rightArray.length > 0) {
if(leftArray[0] < rightArray[0]) {
sortedArray.push(leftArray[0]);
leftArray.shift();
} else {
sortedArray.push(rightArray[0]);
rightArray.shift();
}
}
return sortedArray.concat(leftArray).concat(rightArray);
}
const list = [32, 12, 23, 52, 5, 16, 74, 21, 33, 55, 85];
const sort = mergeSort(list);
sort.next(); // I expected [32, 12], [23, 52, 5]
sort.next(); // [32, 12] and so on...
It turned out the result was not what I expected. I would very much appreciate it if you advise me on the usage of the generator function!
In merge sort, array is divided into smaller arrays till its size is 1. After this, it merge the smaller arrays such a way that the newly created array is also sorted.
To understand recursion you can trace all recursion levels with indentation. For example:
const log = (level, data) => {
var s = ""
for (i = 0; i < level; i++) {
s += " ";
}
console.log(s + data);
}
const merge = (left, right) => {
const result = [];
while(left.length && right.length){
if(left[0] <= right[0]){
result.push(left.shift());
}else{
result.push(right.shift());
}
}
while(left.length) result.push(left.shift());
while(right.length) result.push(right.shift());
return result;
}
const mergeSort = (array, level) => {
log(level, "Start " + array);
if(array.length < 2) {
log(level, "Finish " + array);
return array;
}
const middle = Math.floor(array.length / 2);
log(level, "middle element " + array[middle])
const leftArr = array.slice(0, middle);
const rightArr = array.slice(middle, array.length);
var result = merge(mergeSort(leftArr, level + 1), mergeSort(rightArr, level + 1));
log(level, "Finish " + result);
return result;
};
call the function with level value as 1.