Quick Sort is a popular sorting algorithm that is widely used in computer science. It is known for its efficiency and simplicity, and it is often used as a benchmark for other sorting algorithms.
The algorithm works 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.
Quick Sort was invented by Tony Hoare in 1959 and has since become a fundamental part of computer science.
Algorithm
Here is the algorithm for quick sort:
 Choose a pivot element from the array.
 Partition the array into two subarrays, according to whether they are less than or greater than the pivot element.
 Recursively apply the quick sort algorithm to each subarray.
Partition
The partitioning process starts by selecting a pivot element from the array. There are different ways to choose a pivot element, but one common method is to select the last element of the array. The partitioning process then proceeds as follows:
 Initialize two pointers i and j. Pointer i starts from the beginning of the array and pointer j starts from the beginning of the array.
 Traverse the array with the j pointer, comparing each element with the pivot element.
 If an element less than to the pivot is encountered, swap it with the element at index i, and increment i. This ensures that all elements less than to the pivot are on the left of the pivot.
 Once j reaches the end of the array, swap the pivot element with the element at index i+1. This ensures that the pivot element is in its correct position in the array.
 Return the index of the pivot element.
At the end of the partitioning process, the array is partitioned into two subarrays around the pivot element. The left subarray contains elements less than to the pivot, and the right subarray contains elements greater than of equal to the pivot. These subarrays are then recursively sorted using the same partitioning process until the entire array is sorted.
The partitioning process is a key component of the QuickSort algorithm and has a time complexity of O(n), where n is the size of the array being partitioned. It is also a stable operation, which means that the relative order of equal elements is preserved after the partitioning process.
Implementation of Quick Sort in Python
from typing import List
def partition(arr: List[int], low: int, high: int) > int:
"""Partitions the array into two subarrays.
Elements smaller than the pivot on the left and elements greater than the pivot on the right.
Args:
arr: The array to partition.
low: The starting index of the subarray to partition.
high: The ending index of the subarray to partition.
Returns:
The index of the pivot element.
"""
i = low  1
pivot = arr[high]
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quicksort_inplace(arr: List[int], low: int, high: int) > None:
"""Sorts the given array inplace using the quicksort algorithm.
Args:
arr: The array to sort.
low: The starting index of the subarray to sort.
high: The ending index of the subarray to sort.
"""
if low < high:
pivot = partition(arr, low, high)
quicksort_inplace(arr, low, pivot  1)
quicksort_inplace(arr, pivot + 1, high)
arr = [11, 3, 14, 3, 10, 7, 8, 3, 1, 1, 1, 9, 1, 5]
quicksort_inplace(arr, 0, len(arr)  1)
print("Sorted array:", arr)
Properties of Quick sort

Divide and Conquer
The key idea behind Quick Sort is the Divide and Conquer strategy. The algorithm selects a pivot element from the array and partitions the other elements into two subarrays, according to whether they are less than or greater than the pivot. The subarrays are then recursively sorted using the same algorithm. 
InPlace Sorting
Quick Sort is an inplace sorting algorithm, which means that it does not require any additional memory to perform the sorting. It sorts the array by moving elements around within the array itself, without creating any new data structures. 
Recursive
Quick Sort is a recursive algorithm, which means that it calls itself repeatedly on smaller and smaller subarrays until the base case is reached. In the case of Quick Sort, the base case is when the subarray has fewer than two elements. 
Average and WorstCase Time Complexity
The time complexity of Quick Sort is O(n log n) on average, where n is the length of the array. This means that the algorithm takes approximately n log n operations to sort an array of length n. However, in the worst case, when the pivot element is chosen poorly (for example, if the array is already sorted), the time complexity can be O(n^2). 
BestCase Time Complexity
The bestcase time complexity of Quick Sort is O(n log n), which occurs when the pivot element is chosen such that the two subarrays are of equal size.