Algo Visualizer

The best way to understand complex data structures is to see them in action. This project is developed in an
interactive animations for a variety of data structures and algorithms.

Merge sort

Delay Time :

10

Array Size :

10

Defination :
Merge sort takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by comparing every two elements (i.e., 1 with 2, then 3 with 4...) and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list. Of the algorithms described here, this is the first that scales well to very large lists, because its worst-case running time is O(n log n).

Performance
Best-case Time complexity: O(nlogn)
Average-case Time complexity: O(nlogn)
worst-case Time complexity: O(nlogn)

Space complexity
worst-case Space complexity: O(n) 


        function mergeSort(Arr){
            inPlaceSort(Arr,0,len-1)
        
            async function inPlaceSort(x, first, last){
        
                var left, mid, right, temp;
        
                if(first>=last)	return Promise.resolve();
        
                mid = Math.floor((first+last)/2);
        
                await inPlaceSort(x,first,mid);
                await inPlaceSort(x,mid+1,last);
        
                left = first;
                right = mid+1;
        
                    if(x[mid] <= x[right])	return;
                    
                    while(left <= mid && right <= last){
                        if(x[left] <= x[right]){
                            left++;
                        }
                        else{
                            temp = x[right];
                            await moveArr(x,left,right);
                            x[left] = temp;
                            await drawArr(x);
                            await sleep(time);
                            left++; right++; mid++;
                            }
                        }
                        return Promise.resolve();
                    }
        
            function moveArr(x,left,right){ 
                var tempArr = [];
                for(var i=0, j=left; i<(right-left); i++,j++){
                        tempArr[i] = x[j];
                }
        
                for(var i=0, j=left+1; i<(right-left); i++,j++){
                        x[j] = tempArr[i];
                }
                return Promise.resolve(x);
            }
        }

Designed and built with by The ThunderBolt