How can I show the process of a Merge Sort similiarly to how I did to a Bubble Sort on canvas

Question

Im taking a Highschool CompSci 30 class and I'm working on an assignment. I'm trying to make something that will sort arrays of HSL values and display it on a canvas. I'm using two different algorithms, Bubble sort and Merge sort. My Bubble Sort works just as I want it to, it sorts and shows the process as it's sorting. My Merge Sort also works but I want it to show the process just like my Bubble Sort does. How I got my Bubble Sort to work is by adding async before my function and adding await delay(ms) after each change is made so it draws a new version of the array after however many ms. The code for merge sort is a bit different since its recursive and I'm not sure where to add a draw function or a delay or if that approach would even work.

I've tried adding async and await like I did with my Bubble Sort but the Merge Sort code is more complex and I can't get it right

This is my draw function:

function draw(){
for(y=0;y<361;y++){
hue = cArray[y].slice(4,cArray[y].indexOf(",", 4));
ctx.fillStyle = `hsl(`+ hue + `,100%,50%)`;
ctx.fillRect(x,0,4,canvas.height);
x=x+3;} //draws small strips of color
x=0; //resets after every call
}

My Bubble Sort:

async function bubbleSort(array){
    for(i=0;i<array.length;i++){
        for(j=1;j<array.length;j++){
        var hue1 = array[j-1].slice(4,array[j-1].indexOf(","));
        var hue2 = array[j].slice(4,array[j].indexOf(","));
            if(hueFromHsl(array[j-1]) > hueFromHsl(array[j])){
            var temp = array[j-1];
            array[j-1] = array[j];
            array[j] = temp;
            draw(array);
            }
        }
     await delay(1);
    }
return array;
}

My Merge Sort:

function mergeSort(array){
if (array.length < 2) {return array;}
var mid = Math.floor(array.length / 2);
var left = array.slice(0, mid);
var right = array.slice(mid,array.length);
return merge(mergeSort(left), mergeSort(right));
}

function merge(left,right){
var result = [];
var l = 0, r = 0;
while (l < left.length && r < right.length) {
  if (hueFromHsl(left[l]) < hueFromHsl(right[r])) {result.push(left[l++]);}
   else {result.push(right[r++]);}
    }
return result.concat(left.slice(l)).concat(right.slice(r));
}

Also here is a js.do of the code: https://js.do/Brunsos/color-sort

The process should look similiar to the way my Bubble Sort looks when its used but it either finishes the sort instantly or doesnt work at all. What can I do?

Answer 1

Great code! The issue with displaying this is that it creates copies at each iteration using slice(), so the original array remains the same until the end. Instead of using return statements, just change the actual array. To do this, pass in indexes of the subarrays, then change the actual array. Just call draw(array) within the function. Notice now neither function returns anything, instead they change the array passed in...

async function mergeSort(array, leftIndex, rightIndex) {
    length = rightIndex - leftIndex
    if (length < 2) {
        return array;
    }
    var mid = leftIndex + Math.floor(length / 2);

    mergeSort(array, leftIndex, mid)
    mergeSort(array, mid, rightIndex)      
    await delay(1000*Math.sqrt(rightIndex-leftIndex));
    draw(array)
    merge(array, leftIndex, mid, rightIndex)

}

function merge(array, leftIndex, mid, rightIndex) {
    var result = [];
    var l = leftIndex,
        r = mid;
    while (l < mid && r < rightIndex) {
        if (array[l] < array[r]) {
            result.push(array[l++]);
        } else {
            result.push(array[r++]);
        }
    }
    result = result.concat(array.slice(l, mid)).concat(array.slice(r, rightIndex));
    for (let i = 0; i < rightIndex - leftIndex; i++) {
        array[leftIndex + i] = result[i]
    }
}

Button Script:

<button id="mSort" class="sort" onclick=
"(async() => {
  await mergeSort(cArray,0,360);
  await delay(1600);
  draw(cArray);
})()"
>Merge Sort</button>
</div>

This button script is to allow for the last draw, since the draw occurs before the final merge if you don't await then draw it will be stuck before the final merge...