A suffix array is an array formed by taking a string, and storing pointers to all the suffixes in the array. As an example, if the...
Least Significant Digit Suppose we have \(N\) strings of length \(W\). The idea behind the LSD sort is to first sort the last “digit”...
Counting Sort Suppose we have \(N\) elements, but we know the elements are drawn from a fixed, finite list (called the alphabet in this...
One way to sort a list is to use the heap data structure. Given an array of \(N\) unsorted elements, build a max heap in place. Start...
A quick sort works recursively: Shuffle the list. This protects against a carefully crafted input that will make the algorithm...
Say you have \(N\) points on a Euclidean plane. You want to find the polygon with the smallest area that can be formed connecting a...
Any comparison based sorting algorithm must use at least \(\lg(N!)\sim N\lg N\) comparisons for the worst case. This is absent any...
A merge sort works recursively: Split the list into two roughly equal halves. Sort each half using mergesort. Merge the two...
A shell sort works somewhat recursively. It first sorts every \(k\) elements (i.e. the sublist formed by elements 0, \(k\), \(2k\),...
An insertion sort starts from the first element in the list, and then for each element will check with the previous one to see if it is...
An inversion in a list of elements is a pair of elements where the 2nd element is smaller than the first (i.e. the 2nd element would be...
A selection sort starts out by traversing the whole list, finding the minimal element, and swapping it with the first element. It then...