Shell Sort

Shell Sort is a highly effecient sorting algorithm. The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared.

Time Complexity: Generally depends on the gap sequence.
For many practical variants of gap sequence, determining their time complexity remains an open problem.
But for the best known gap sequence, the time complexity is O(n log²n).

Code

            
    elem=document.querySelector(".example-container");
    setCanvas(elem);
    arr=[];
    for(i=0;i<WIDTH/2;i++){
        arr.push(random(0,HEIGHT));
    }
    k=0;
    interval=floor(arr.length/2);

    function draw(){
        clearCanvas();
        
        if(interval>0){

            for(i=interval;i<arr.length;i++){
                temp=arr[i];
                for (j = i; j >= interval && arr[j-interval] > temp; j-=interval)  {
                    arr[j] = arr[j-interval];
                }
                arr[j]=temp;
            }
        }
        
        for(i=0;i<arr.length;i++){
            x=mapRange(i,0,arr.length,0,WIDTH);
            new line(x,HEIGHT,x,HEIGHT-arr[i],'#695fe6',2);
        }
        interval=floor(interval/2);

        requestAnimationFrame(draw);
    }
    draw();