Sorting Algorithms
Terminology
A sorting algorithm is said to be stable if it maintains the relative order of equal elements. This means that if two elements
A sorting algorithm is said to be in-place if it performs the sorting by mutating the input list. In a lot of cases. In a lot of cases this is a desirable property, as it allows the algorithm to avoid allocating additional memory.
The lower bound of comparison-based sorting
For any comparison-based sorting algorithm, there exists a lower bound on the number of comparisons required to sort the input list at
We will see that some algorithms surpass this lower bound, but that is only possible because of assumptions on the input list that the algorithms make. Bucket Sort is one such algorithm that assumes the input list is uniformly distributed.
The CLRS book provides a mathematical proof of the lower bound on page 207.
Algorithms
This section explores various sorting algorithms and their properties.
- Insertion Sort is a simple iterative sorting algorithm
- Quicksort is a popular divide-and-conquer algorithm
- Merge Sort is a divide-and-conquer algorithm that is stable
- Bucket Sort breaks the lower bound by assuming a uniform distribution