Sorting Algorithms

My first python class was actually very helpful. Link to various sorting algorithms implemented in Python.

Algorithm	Best Case(Ω)	Average Case(Θ)	Worst Case(O)
Selection Sort	$O (n^{2})$	$O (n^{2})$	$O (n^{2})$
Insertion Sort	$O (n)$	$O (n^{2})$	$O (n^{2})$
Bubble Sort	$O (n)$	$O (n^{2})$	$O (n^{2})$
Merge Sort	$O (n)$	$O (n lo g n)$	$O (n lo g n)$
Quick Sort	$O (n lo g n)$	$O (n lo g n)$	$O (n^{2})$
Heap Sort	$O (n lo g n)$	$O (n lo g n)$	$O (n lo g n)$
Radix Sort	$O (nk)$	$O (nk)$	$O (nk)$
Counting Sort	$O (n + k)$	$O (n + k)$	$O (n + k)$
Bucket Sort

Quicksort is likely faster in practice, but merge sort is faster on paper.
Merge Sort divides the set into the smallest possible groups immediately then reconstructs the incrementally as it sorts the groupings.
Quicksort continually partitions the data set by a pivot, until the set is recursively sorted

You can do something like the following

sort(begin(arr), end(arr), [](string &s1, string &s2){ return s1+s2>s2+s1; });

sort(v.begin(), v.end());

Using the greater operator

sort(arr, arr + n, greater<int>());

🛠️ Steven Gong