Quick Sort

Thinking:

when we don’t have special knowledge about certain set of unsorted data the best we can do is O(n*log(n)), like using quick or merge sort, the fastest sorting algorithms. In a recursion we are going to be able to split the inputs for merge sort up to log(n) levels of work.

const QuickSort = (arr, startIndex, endIndex) => {
  if (startIndex < endIndex) {
    let pivotIndex = Partition(arr, startIndex, endIndex)
    QuickSort(arr, startIndex, pivotIndex - 1)
    QuickSort(arr, pivotIndex + 1, endIndex)
  }
}

const Partition = (arr, startIndex, endIndex) => {
  let pivotValue = arr[endIndex]
  let i = startIndex

  for (let j = startIndex; j < endIndex; j++) {

    if (arr[j] < pivotValue) {
      Swap(arr,i , j)
      i++
    }
  }
  Swap(arr,i, endIndex)
  return i
}

const Swap = (arr, index1, index2) => {
  let temp =arr[index1]
  arr[index1] =arr[index2]
  arr[index2] = temp
}

let QuickSort = (arr, low, high) => {
  if (low < high) {
    let p = Partition(arr, low, high);
    QuickSort(arr, low, p - 1);
    QuickSort(arr, p + 1, high);
  }
  return arr;
}