Mergesort

Recursive. This breaks the array into 2 smaller arrays, then those into 2 more smaller arrays, and continues until the base case of an array of size 1 is reached, then merges these auxiliary arrays in sorted order. This ends up being efficient since each auxiliary array going up the call stack will already be in sorted order.

Time Complexity: Theta(n*log(n))

Space Complexity: O(n)

------------------------------------------------------------------------------------------------------

Insertion Sort

For each element, insert it into the sorted portion by pushing it back until it's in the proper spot.

Time Complexity: Omega(n), Theta(n^2), O(n^2)

Space Complexity: O(1)

------------------------------------------------------------------------------------------------------

Selection Sort

Go through the unsorted portion of the array to select the next smallest element, and swap with the current.

Time Complexity: Theta(n^2)

Space Complexity: O(1)

------------------------------------------------------------------------------------------------------

Bubble Sort

Compare side by side elements and swap if the left one is larger; with each trial of this the next largest element 'bubbles' to the top. This needs to be done for n passes, since each pass only brings the next largest element to the top.

Time Complexity: Omega(n), Theta(n^2), O(n^2)

Space Complexity: O(1)

------------------------------------------------------------------------------------------------------

Quicksort

Recursive. For each call, a random element (we refer to as the pivot) is chosen and all elements less than it are placed to the left, and all elements greater are placed to the right. It is then recursively called on both of those two halves. A partition function is called in each iteration to select the pivot, which can make it either a random selection or a fixed array index (here it is fixed, the last index).

Time Complexity: Omega(n*log(n)), Theta(n*log(n)), O(n^2)

Space Complexity: O(n*log(n))

------------------------------------------------------------------------------------------------------

Heapsort

This forms a max heap (a tree but with the condition that a parent is greater than a child), and for each node starting from the last leaf, switches it with the root node and calls a function called heapify, which restructures the tree so that the max element is on top again. Each time a max element is removed, it is essentially at the end of an array; in other words, is now in sorted position. It should be noted that heapsort itself is not recursive, but it calls heapify which is.

Time Complexity: Theta(n*log(n))

Space Complexity: O(1)

------------------------------------------------------------------------------------------------------

Counting Sort

Creates two new arrays, one counting the frequency of occurrence of each number in the array (then adjusted to represent the array index), and the other to hold the output array. The output array at index i is updated with the value of indexarray[originalarray[i]] for each i in range n. This results in linear runtime, but it only works if the range of numbers is known beforehand. This is also a stable sort, meaning the order of repeated values doesn't change.

Time Complexity: Theta(n+k), k=range of possible values

Space Complexity: O(k)

------------------------------------------------------------------------------------------------------

Radix Sort

This will first sort all elements by the digit in the 1's place, then by the digit in the 10's place.. continuing through to the last digit. The sorting is done with some stable sorting algorithm (counting sort, for example). It may seem more natural to sort by the largest digit first down to the 1's place but this mathematically will not work.

Time Complexity: Theta(d(n+k)), d=max # of digits, k=base of whatever number we are using (usually 10)

Space Complexity: O(n+k)

------------------------------------------------------------------------------------------------------

Bucket Sort

Adjust input so that they are all in range [0:1), and divide range into buckets where certain ranges of values will go. Each of these buckets, which are ideally near-sorted, are then sorted using insertion sort and concatenated.

Time Complexity: Omega(n+k), Theta(n+k), O(n^2), k=# of buckets

Space Complexity: O(n)

------------------------------------------------------------------------------------------------------

Bogosort

Creates a random permutation the array and sees if it is sorted or not; repeats this until sorted. You would never use this in real life, it is just a common thought experiment that I included for fun.

Time Complexity: Omega(0), Theta(n*(n!)), O(Infinity)

Space Complexity: O(1)

------------------------------------------------------------------------------------------------------