Merge Sort

Merge sort is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output. Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945. A detailed description and analysis of bottom-up merge sort appeared in a report by Goldstine and von Neumann as early as 1948.

Conceptually, a merge sort works as follows:

1. Divide the unsorted list into n sublists, each containing one element (a list of one element is considered sorted).
2. Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list.

function mergeSort(array) {
  const half = array.length / 2;
  if(array.length < 2){
    return array
  }
  const left = array.splice(0, half);
  return merge(mergeSort(left),mergeSort(array));
}
function merge(left, right) {
    let arr = []
    while (left.length && right.length) {
        if (left[0] < right[0]) {
            arr.push(left.shift())
        } else {
            arr.push(right.shift())
        }
    }
    return [ ...arr, ...left, ...right ]
}
        

Time complexity of Merge Sort is O(n*Log n) in all the 3 cases (worst, average and best)

Quick Sort

Quicksort is a type of divide and conquer algorithm for sorting an array, based on a partitioning routine. The details of this partitioning can vary somewhat, so that quicksort is really a family of closely related algorithms.

The steps for in-place quicksort are:

1. If the range has less than two elements, return immediately as there is nothing to do. Possibly for other very short lengths a special-purpose sorting method is applied and the remainder of these steps skipped.
2. Otherwise pick a value, called a pivot, that occurs in the range
3. Partition the range: reorder its elements, while determining a point of division, so that all elements with values less than the pivot come before the division, while all elements with values greater than the pivot come after it; elements that are equal to the pivot can go either way
4. Recursively apply the quicksort to the sub-range up to the point of division and to the sub-range after it, possibly excluding from both ranges the element equal to the pivot at the point of division

function quickSort(array){
    if (array.length <= 1) {
        return array;
    }
    const pivot = array[0];
    let left = [], right = [];
    for(let i=1;i < array.length;i++){
        array[i] < pivot ?
            left.push(array[i]) : right.push(array[i]);
    }
    return quickSort(left).concat(pivot, quickSort(right));
}
        

The average and best-case time complexity for quicksort(simple partition) is O(n log(n)). The worst-case performance is O(n^2).

Heap Sort

Heapsort is a comparison-based sorting algorithm. It can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region. Heap sort maintains the unsorted region in a heap data structure to more quickly find the largest element in each step.

let heapLength;
function heapSort(length){
    heapLength = length;
    let array = initArray(heapLength);
    for(let i = Math.floor(heapLength/2);i>=0;i--){
        heapRoot(i, array);
    }
    for (let i = heapLength - 1; i > 0; i--) {
        swap(array, 0, i);
        heapLength--;
        heapRoot(0, array);
    }
}

function heapRoot(i, array){
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    let max = i;
    if(left < heapLength && array[left].value > array[max].value){
        max = left;
    }
    if(right < heapLength && array[right].value > array[max].value){
        max = right;
    }
    if(max !== i){
        swap(array, i, max);
        heapRoot(max, array)
    }
}

function swap(input, a, b){
    let temp = input[a];
    input[a] = input[b];
    input[b] = temp;
}
        

Time complexity of Heap Sort is O(n*Log n) in all the 3 cases (worst, average and best)