QUICK SORT

Quick sort utilizes a divide and conquer method. It divides a list at a pivot point, breaking it into smaller parts to perform sorting operations on them. This is where the recursion comes in, quicksort calls itself to sort the smaller lists after they are split at the pivot point. This will repeat until the sub-arrays are broken down to one element. Also, keep in mind there are multiple ways to write this algorithm.

function swap(arr, a, b){
    let temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp
}
            
function partition(arr, start, end){
    let pivotIndex = start;
    let pivotValue = arr[end];
    for (let i = start; i < end; i++) {
        if (arr[i] < pivotValue) {
            swap(arr, i, pivotIndex);
            pivotIndex++;
        }
    }
    swap(arr, pivotIndex, end);
    return pivotIndex;
}
        
function quickSort(arr,start,end) {
    if (start >= end) {
        return;
    }
    let index = partition(arr,start,end);
    quickSort(arr,start,index - 1);
    quickSort(arr,index + 1, end)
    return arr
}

• If the array has fewer than 2 elements it is returned immediately.
• Next it calls the partition function which moves all values less than the pivot value to its left and all values greater than the pivot value move to its right.
• Inside the Partition function, the value in the last index will always be the pivotValue and the pivotIndex will start as the first index and move right one spot for every element that is less than the pivotValue.
• The for loop checks if each element is less than the pivotValue.
• If the element is less than the pivotValue it swaps places with the element in the pivotIndex, then the pivotIndex moves up one index to the right to keep the lesser values to its left.
• If the element is greater than the pivotValue, nothing changes.
• When the loop reaches the pivotValue, it's value is swapped with the value of the pivotIndex.
• Now the pivotValue is in the pivotIndex and all values less than the pivotValue are on its left and all larger values are on its right.
• The Partition function returns the pivotIndex and quicksort calls itself two times.
• Once with the elements on the left side of the pivotIndex and once with the elements on the right side.
• This process repeats until the subarrays are broken down to one element.
• Now the original condition can't be met which allows the function to stop running.
• Since the subarrays have been sorted in place, the array is now completely sorted.