Unable to vizualize a sorted array while implementing mergesort

p5.js Coding Questions
1

I tried to implement a mergesort algorithm but the array isn’t getting sorted for some reason.The expected output is a sorted array of lines displayed on the browser window.

Here is my code

var values = []

function setup(){
   createCanvas(600,400);
   values.length = width;
   for(let i=0; i<values.length; i++){
	  values[i] = random(height);
   }
mergesort(values, 0, values.length-1)
}

function draw(){
   background(0);
   for (let i=0; i< values.length; i++){
	  stroke(255,0,255);
	  line(i, height, i, height - values[i]);
   }
 }
 function mergesort(arr, start, end){
    if (start < end){

      let middle = (start + (end-1))/2;
  
     merge(arr, start, middle, end);
     mergesort(arr, start, middle);
     mergesort(arr, middle +1, end);
     }
}

function merge(arr, start, middle, end){
   let sizeL = middle-start +1;
   let sizeR = end - middle;
   let arrL = [];
   let arrR = [];
   //var arr1 = [];
   for (let i = start; i < sizeL; i++) 
      arrL.push(arr[i])
   for (let j = start; j < sizeR ; j++) 
      arrR.push(arr[j])

   let a = start; 
   let b = start;
   let k = start + 1;
   while ( a< sizeL && b < sizeR){
 	  if (arrL[a] <= arrR[b]){
    	 arr[k] = arrL[a]; 
         a++; 
       } 
       else{
          arr[k] = arrR[b]; 
          b++; 
       } 
       k++; 
    } 

    while(a < sizeL){ 
       arr[k] = arrL[a]; 
       a++; 
       k++; 
   } 
   while(b < sizeR) { 
       arr[k] = arrR[b]; 
       b++; 
       k++; 
}
   //return arr1;

}

1 Like
2

Welcome to the forums! Whether or not this is hw, I encourage you to take a little more time to bug test. Problem solving in general is a really valuable skill.

Specifically, seeing that you have two functions, merge(), and mergesort(), try testing each function individually. Another good idea is to start with really small test-cases that you can trace by hand.

Hope this helps!

1 Like
3

My familiarity with java script is pretty low. I have been trying to rectify my code for quite sometime now with little success. Initially I got a stack limit exceeded error and now this.
I will try to test the two functions separately like you suggested.
Thank you tony.

1 Like
4

If you’re more familiar with a strongly-typed language like Java or C++, Javascript definitely takes some getting used to. All i can really say is it takes practice (and a lot of debugging and a lot of stackoverflow :rofl:)

5

Hey guys, I found the solution to the problem.
Here is the final working program:

3 Likes