Sorting algorithms

// https://www.google.com/search?q=sorting+algorithms&sxsrf=ALiCzsbgLckE8GgnpMt0DT6Fq05YjFdrWw%3A1663748288817&ei=wMgqY7O-MYu8kwXqrLigBA&ved=0ahUKEwiznoCuuaX6AhUL3qQKHWoWDkQQ4dUDCA4&uact=5&oq=sorting+algorithms&gs_lcp=Cgdnd3Mtd2l6EAMyBAgAEEMyBQgAEIAEMgUIABCABDIFCAAQgAQyCggAEIAEEIcCEBQyBQgAEIAEMgUIABCABDIFCAAQgAQyBQgAEIAEMgUIABCABDoECCMQJzoFCAAQkQI6CggAELEDEIMBEEM6DgguELEDEIMBEMcBENEDOgsIABCABBCxAxCDAToHCAAQyQMQQzoLCC4QgAQQxwEQrwFKBAhBGABKBAhGGABQAFiqImDQI2gAcAF4AIAB8wGIAeIPkgEGMTAuNy4xmAEAoAEBwAEB&sclient=gws-wiz

// JavaScript program for Merge Sort
// https://www.geeksforgeeks.org/merge-sort/
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
var arr = [4, 8, 7, 2, 11, 1, 3, 34, 5, 666, 3, 1, 55];

var merge = function(l1, r1) {
    var merged = [];

    while(l1.length > 0  && r1.length > 0 ) {
        if(l1[0] < r1[0]) {
            merged.push(l1.shift());
        }
        else {
            merged.push(r1.shift());
        }
    }

    return merged.concat(l1,r1);
}

var mergeSort = function(arr) {
    if(arr.length < 2) {
        return arr;
    }
    var middle = parseInt(arr.length / 2);
    var l1 = arr.slice(0,middle);
    var r1 = arr.slice(middle);
    l1 = mergeSort(l1);
    r1 = mergeSort(r1);
    return merge (l1, r1);
}
debugger;
var sortedM = mergeSort(arr);
console.log(sortedM);

//////////////////////////////////////////
// Quick sort
// https://stackabuse.com/quicksort-in-javascript/

function quicksort(array) {
    if (array.length <= 1) {
      return array;
    }

    var pivot = array[0];

    var left = [];
    var right = [];

    for (var i = 1; i < array.length; i++) {
      array[i] < pivot ? left.push(array[i]) : right.push(array[i]);
    }

    var l1 = quickSort(left);
    var r1 = quickSort(right)
    return l1.concat(pivot, r1);

};
debugger;
var unsorted = [23, 45, 16, 37, 3, 99, 22];
var sorted = quicksort(unsorted);

console.log('Sorted array', sorted);

//////////////////////////////////////////
// Bubble sort Implementation using Javascript


// Creating the bblSort function
function bblSort(arr){

    for(var i = 0; i < arr.length; i++){

      // Last i elements are already in place
      for(var j = 0; j < ( arr.length - i -1 ); j++){

        // Checking if the item at present iteration
        // is greater than the next iteration
        if(arr[j] > arr[j+1]){

          // If the condition is true then swap them
          var temp = arr[j]
          arr[j] = arr[j + 1]
          arr[j+1] = temp
        }
      }
    }
    // Print the sorted array
    console.log(arr);
}


// This is our unsorted array
var arr = [234, 43, 55, 63,  5, 6, 235, 547];


// Now pass this array to the bblSort() function
bblSort(arr);

// Insertion sort
// https://www.geeksforgeeks.org/insertion-sort/

// Javascript program for insertion sort

// Function to sort an array using insertion sort
function insertionSort(arr, n)
{
    let i, key, j;
    for (i = 1; i < n; i++)
    {
        key = arr[i];
        j = i - 1;

        /* Move elements of arr[0..i-1], that are
        greater than key, to one position ahead
        of their current position */
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

// A utility function to print an array of size n
function printArray(arr, n)
{
    let i;
    for (i = 0; i < n; i++)
        console.log(arr[i] + " ");
}

// Driver code
let arr = [12, 11, 13, 5, 6 ];
let n = arr.length;

insertionSort(arr, n);
printArray(arr, n);

// This code is contributed by Mayank Tyagi

// JavaScript program for implementation
// of Heap Sort
// https://www.geeksforgeeks.org/heap-sort/?ref=lbp

function sort( arr)
{
    var N = arr.length;

    // Build heap (rearrange array)
    for (var i = Math.floor(N / 2) - 1; i >= 0; i--)
        heapify(arr, N, i);

    // One by one extract an element from heap
    for (var i = N - 1; i > 0; i--) {
        // Move current root to end
        var temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // call max heapify on the reduced heap
        heapify(arr, i, 0);
    }
}

// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
function heapify(arr, N, i)
{
    var largest = i; // Initialize largest as root
    var l = 2 * i + 1; // left = 2*i + 1
    var r = 2 * i + 2; // right = 2*i + 2

    // If left child is larger than root
    if (l < N && arr[l] > arr[largest])
        largest = l;

    // If right child is larger than largest so far
    if (r < N && arr[r] > arr[largest])
        largest = r;

    // If largest is not root
    if (largest != i) {
        var swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;

        // Recursively heapify the affected sub-tree
        heapify(arr, N, largest);
    }
}

/* A utility function to print array of size n */
function printArray(arr)
{
    var N = arr.length;
    for (var i = 0; i < N; ++i)
        document.write(arr[i] + " ");

}


var arr = [12, 11, 13, 5, 6, 7];
var N = arr.length;

sort(arr);

document.write( "Sorted array is");
printArray(arr, N);


// This code is contributed by SoumikMondal