Quicksort
Quicksort is one of the most effective sorting algorithms which developed by British computer scientist Tony Hoare in 1959. Quicksort is a 'divide and conquer' algorithm that, on average, sorts n items in O(n log n) time, which make it one of the most preferred sorting algorithms in various programming languages, despite its worstcase time complexity being O(n^2).
Visualization
How Does It Work?
Quicksort operates by selecting a 'pivot' element from the array and partitioning the other elements into two subarrays, according to whether they are less than or greater than the pivot. The subarrays are then recursively sorted.

Partitioning: Choose an element from the array to serve as a pivot and put the pivot in the right sorted position. Although there are many strategies to select the pivot, a common practice is to choose the last element in the array.

Recursive Sort: Recursively apply the above steps to the left subarray of elements with smaller values and to the right subarray of elements with larger values. Do nothing if the subarray contains only 1 or no element.
Strengths and Weaknesses
Quicksort's main strength lies in its efficiency in handling large datasets. The recursive approach, dividing the problem into smaller, simpler problems, is part of why Quicksort is effective. On average, it outperforms other popular sorting algorithms like Bubble Sort, Insertion Sort, and Selection Sort, especially for large arrays.
Quicksort is an inplace sorting algorithm, meaning it sorts the input array using a small, constant amount of extra space. Therefore, its space complexity is O(log n).
However, its performance is greatly influenced by the choice of the pivot. If the pivot is consistently the smallest or largest element, the partitioning will result in one very small and one very large subarray, leading to its worstcase time complexity of O(n^2). This typically occurs when the input array is already sorted or sorted in reverse order.
To mitigate this issue, a technique known as 'median of three' may be used, where the pivot is chosen as the median of the first, middle, and last elements of the array. This strategy tends to produce more balanced partitions and brings the time complexity closer to the ideal O(n log n).
Application
Quicksort's efficiency makes it a preferred choice in many realworld applications. It is used in programming languages like C and Python for inbuilt sorting functions. Additionally, it plays a significant role in computer graphics for rendering, database management for query execution, and machine learning for data preprocessing, among others.
Implementation
// QuickSort sorts array of items
export function quickSort(a: number[]) {
sort(a, 0, a.length  1)
}
function swap(a: number[], i: number, j: number) {
const tmp = a[i]
a[i] = a[j]
a[j] = tmp
}
function sort(a: number[], low: number, high: number) {
if (low < high) {
const pi = partition(a, low, high)
sort(a, low, pi1)
sort(a, pi+1, high)
}
}
function partition(a: number[], low: number, high: number): number {
const pivot = a[high]
// find first position i where a[i] >= pivot (could be pivot position itself)
let i = low
while (a[i] < pivot) {
i++
}
// up to the position prior to the pivot, if found element smaller than pivot then move it to the left
for (let j = i + 1; j < high; j++) {
if (a[j] < pivot) {
swap(a, i, j)
i++
}
}
// swap pivot with i
if (i < high) swap(a, i, high)
return i
}