Whats goin on?

Quick sort is another recursive algorithm, however, works quite differently to merge sort. First, a random element in the input array is designated as the pivot. In this case, the pivot is always the last element of the input array. Next the function iterates through the entire array and sorts it in-place into two arrays: 1. Values smaller than the pivot. 2. Values larger than the pivot. Then the algorithm places the pivot in the correct space in between and is called on the subsequent groups and is repeated until the entire array has been sorted. In this example, the function achieves this by initializaing a low index and current element as 0, the first element in the array. If the current element is smaller than the pivot, it is swapped with the element at the low position and the current element is incremented to the next position. If the element is larger than the pivot, it moves on to the next element without updating the low position. After the entire array has been covered, the pivot is then swapped with the element right after the low position. The algorithm is then called again on the two sections, one from the start of the smaller section to the pivot and one from the pivot to the end of the larger section. This process is repeated until the entire array has been sorted.

Performance

Time complexity

Because each subsequent call iterates through the entire array, and each subsequent array is approximately half of the original, the time complexity of this algorithm is

O(nlog(n))

Space complexity

Quick sort creates a stack for each call of the function which only needs to be called on each array. The number of arrays decreases logarithmically so the space complexity is

O(log(n))

More Info...