I remember reading a retweet from Elon Musk about what he called an "interesting sorting algorithm" where to sort one would launch $n$ concurrently running threads, at the same time, one for each item to sort. Each thread then sleep for the amount which it is to sort, inserting it into a new array when that time amount has passed. The end result is a sorted array.

I agree that it is an interesting sorting algorithm, but it didn't seem too efficient. So, I decided to dive into some of the most popular sorting algorithms.

# Bubble Sort

Being a pretty simple, intuitive, and simple to implement, bubble sort is popular. The basic premise behind bubble sort is to iterate through the array, multiple times, and if a value is more than that of the value prior, swap them.

The computational complexity range from $O(n)$ to $O(n^2)$. The average begin $O(n^2)$, making it slower than most sorting algorithms. The implementation presented here is an optimized version of bubbleSort described in the wikipedia page for Bubble Sort.

```
template <class RandomIt>
void bubblesort(RandomIt first, RandomIt last) {
typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
using std::swap;
diff_t n = last - first;
diff_t newn;
while( n > 1 ) {
newn = 0;
for (diff_t i = 1; i < n; i++) {
if (first[i - 1] > first[i]) {
swap(first[i - 1], first[i]);
newn = i;
}
}
n = newn;
}
}
```

The function is a template function, meaning that you could probably use it with almost any STL container of almost any type of number. And, the compiler will generate code for each of them.

An example usage, using the `std::vector<float>`

container

```
std::vector<float> vect;
// fill vector
bubblesort(vect.begin(), vect.end());
```

# Gnome Sort

Also called stupid sort, it is the simplest sorting algorithm out there. Basically, if two elements are already sorted move forward, if two elements are not sorted then swap them and move backward.

It's computational complexity if similar to that of bubble sort where the range of complexity is in the range $O(n)$ to $O(n^2)$ with the average being $O(n^2)$.

```
template <class RandomIt>
void gnomesort(RandomIt first, RandomIt last) {
typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
using std::swap;
diff_t begin = 1;
diff_t n = last - first;
while (begin < n) {
if (first[begin - 1] <= first[begin])
begin++;
else {
swap(first[begin - 1], first[begin]);
if (--begin == 0)
begin = 1;
}
}
}
```

# Heap Sort

Heap sort divides the array to be sorted into a sorted and unsorted areas, it finds the largest element in the unsorted section and moves it to the growing sorted section. Heap sort uses the heap data structure to find the max of the unsorted section.

The algorithm first builds a heap then grabs the largest element of the heap and places it in the sorted section repeatedly. To first build the heap, binary tree, you place items in an order where their value is less or greater than the parent node. It is a fairly fast sorting algorithm with a worst possible complexity of $O(n\log n)$ and best $O(n)$

Geeks for Geeks has a great implementation, so why reinvent the wheel. I just did a couple of modification to have it work with iterators.

```
template <class RandomIt>
void heapify(RandomIt first, typename std::iterator_traits<RandomIt>::difference_type n,
typename std::iterator_traits<RandomIt>::difference_type i) {
typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
using std::swap;
diff_t largest = i;
diff_t l = 2 * i + 1;
diff_t r = 2 * i + 2;
if (l < n && first[l] > first[largest])
largest = l;
if (r < n && first[r] > first[largest])
largest = r;
if (largest != i) {
swap(first[i], first[largest]);
heapify(first, n, largest);
}
}
template <class RandomIt>
void heapsort(RandomIt first, RandomIt last) {
typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
using std::swap;
diff_t n = last - first;
for (diff_t i = n / 2 - 1; i >= 0; i--)
heapify(first, n, i);
for (diff_t i = n - 1; i >= 0; i--) {
swap(first[0], first[i]);
heapify(first, i, 0);
}
}
```

# Insertion Sort

Insertion Sort, another simple sort, basically iterates through, moving elements to where they belong until sorted. It has a complexity ranging from $O(n)$ to $O(n^2)$ with an average $O(n^2)$ complexity.

```
template<class RandomIt>
void insertionsort(RandomIt first, RandomIt last) {
typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
typedef typename std::iterator_traits<RandomIt>::value_type val_t;
diff_t n = last - first;
for (diff_t i = 1; i < n; i++) {
val_t x = first[i];
diff_t j = i - 1;
for (; j >= 0 && first[j] > x; j--)
first[j + 1] = first[j];
first[j + 1] = x;
}
}
```

# Shell Sort

This sort is use full since it has a small memory space compared to it's reasonably low worst possible complexity of $O(n^{\frac{4}{3}})$and best complexity of $O(n\log n)$, depending on the gap chosen. In my implementation I use A036562 as the gap sizes.

Shell Sort is similar to Insertion Sort in that you iterate through the array moving elements to where they belong, but the difference is that you compare values where the values have a set gap and as you iterate the gap decreases.

```
template<class RandomIt>
void shellsort(RandomIt first, RandomIt last) {
typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
typedef typename std::iterator_traits<RandomIt>::value_type val_t;
diff_t n = last - first;
diff_t gap[13] = {16783361, 4197377, 1050113, 262913, 65921, 16577, 4193, 1073, 281, 77, 23, 8, 1};
for (diff_t g = 12; g >= 0; g--) {
for (diff_t i = gap[g]; i < n; i += 1) {
val_t tmp = first[i];
diff_t j;
for (j = i; j >= gap[g] && first[j - gap[g]] > tmp; j -= gap[g])
first[j] = first[j - gap[g]];
first[j] = tmp;
}
}
}
```

# Merge Sort

With the Merge Sort Algorithm, we split the list/array into sub-lists, each with 1 element. Merge each sub-list into larger, sorted, sub-list, until there remains 1 sub-list, which is sorted. The implementation presented requires $n$ memory, larger than other algorithms. It's complexity is pretty much constant at $O(n\log n)$. more info

```
template<class RandomIt>
void ButtomUpMerge(RandomIt first, typename std::iterator_traits<RandomIt>::difference_type iLeft,
typename std::iterator_traits<RandomIt>::difference_type iRight,
typename std::iterator_traits<RandomIt>::difference_type iEnd,
typename std::iterator_traits<RandomIt>::value_type Bfirst[]) {
typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
typedef typename std::iterator_traits<RandomIt>::value_type val_t;
diff_t i = iLeft, j = iRight;
for (diff_t k = iLeft; k < iEnd; k++) {
if (i < iRight && (j >= iEnd || first[i] <= first[j])) {
Bfirst[k] = first[i];
i++;
} else {
Bfirst[k] = first[j];
j++;
}
}
}
template<class RandomIt>
void mergesort(RandomIt first, RandomIt last) {
typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
typedef typename std::iterator_traits<RandomIt>::value_type val_t;
using std::copy;
using std::min;
diff_t n = last - first;
val_t *B = new val_t[n];
for (diff_t width = 1; width < n; width = 2 * width) {
for (diff_t i = 0; i < n; i += 2 * width) {
ButtomUpMerge(first, i, min(i + width, n), min(i + 2 * width, n), B);
}
copy(B, B + n, first);
}
delete[] B;
}
```

# Selection Sort

This sorting algorithm has a constant computational complexity, but it has a memory foot print of one item. It cuts a list into two parts, a sorted and unsorted area. The algorithm finds the smallest or largest element and places it in the sorted area.

```
template<class RandomIt>
void selectionsort(RandomIt first, RandomIt last) {
typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
using std::swap;
diff_t i, j;
diff_t n = last - first;
for (j = 0; j < n - 1; j++) {
diff_t iMin = j;
for (i = j + 1; i < n; i++) {
if (first[i] < first[iMin])
iMin = i;
}
if (iMin != j)
swap(first[j], first[iMin]);
}
}
```

# Odd-Even Sort

Easily parallelizable and relatively simple algorithm; It's computational complexity will range from $O(n)$ to $O(n^2)$ with an average of $O(n^2)$. It's memory foot print is 1 item.

The algorithm compares odd indexed items with a consecutive even indexed items, swapping them if they are not sorted. It, then, alternates between even/odd pairs and odd/even pairs while iterating though the list until it is all sorted.

```
template<class RandomIt>
void oddevensort(RandomIt first, RandomIt last) {
typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
using std::swap;
bool sorted = false;
diff_t n = last - first;
while (!sorted) {
sorted = true;
for (diff_t i = 1; i < n - 1; i += 2) {
if (first[i] > first[i + 1]) {
swap(first[i], first[i + 1]);
sorted = false;
}
}
for (diff_t i = 0; i < n - 1; i += 2) {
if (first[i] > first[i + 1]) {
swap(first[i], first[i + 1]);
sorted = false;
}
}
}
}
```

# Comb Sort

Comb Sort is basically an improvement on bubble sort, but it starts with a fairly large gap in order to move large items from the end of the list to the beginning and slowly decreasing the gap, while iterating, until the list is sorted.

It has a computation complexity range of $O(n\log n)$ to $O(n^2)$, comparatively slow, but with a memory foot print of 1 item.

```
template<class RandomIt>
void combsort(RandomIt first, RandomIt last) {
typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
using std::floor;
using std::swap;
diff_t n = last - first;
diff_t gap = n;
double shrink = 1.3;
bool sorted = false;
while (!sorted) {
gap = static_cast<diff_t>(floor(gap / shrink));
if (gap <= 1) {
gap = 1;
sorted = true;
}
for (diff_t i = 0; i + gap < n; i++) {
if (first[i] > first[i + gap]) {
swap(first[i], first[i + gap]);
sorted = false;
}
}
}
}
```

# Stability

Another aspect of sorting algorithm to consider is whether it is stable. A sorting algorithm is stable if identical items order when placed next to each other retain their order, only between each other. This is useful when the objects being compared has other information that is not being compared in the formation of the sorted list.

Algorithm | Stable |
---|---|

Bubble Sort | yes |

Gnome Sort | yes |

Heap Sort | no |

Insertion Sort | yes |

Shell Sort | no |

Merge Sort | yes |

Selection Sort | no |

Odd-even Sort | yes |

Comb Sort | no |

# Run Times

I went ahead and compile the above code along along with some timing code with randomly generated numbers in an `std::vector<double>`

object with 10,000 items in order to test the times required the for each sorting algorithm. I timed each algorithm thrice and averaged the runs.

Algorithm | Run 1 (μs) | Run 2 (μs) | Run 3 (μs) | Average (μs) |
---|---|---|---|---|

std::sort | 821 | 842 | 874 | 846 |

Bubble Sort | 185253 | 204338 | 186752 | 192115 |

Gnome Sort | 104311 | 11714 | 103302 | 73109 |

Heap Sort | 1215 | 1436 | 1185 | 1279 |

Insertion Sort | 19850 | 21070 | 19474 | 20131 |

Shell Sort | 26442 | 27967 | 26274 | 26894 |

Merge Sort | 1054 | 1240 | 1019 | 1104 |

Selection Sort | 46285 | 50931 | 46937 | 48051 |

Odd-even Sort | 104376 | 113572 | 109559 | 109269 |

Comb Sort | 1121 | 1344 | 1109 | 1191 |