O(N2):
- Insertionsort
For each element it searches the whole array before the element's index
and puts it in the right place and move all the next elements to the right.
- Selectionsort
Searches for the smallest element and put it in the right place and then
move all the others to right.
- Bubllesort
Goes through the array, if the current element is bigger than the next one,
swaps it. It does that until there's no more elements to swap.
O(N Log N):
- Heapsort
It uses a data structure called a heap (the parent must be bigger than the
children) and it is useful for sorting a binary tree in an array. It is not parallelizable.
- Quicksort
It takes a dividing item and separate the items between before and after
the dividing item. It is parallelizable. Worst case is O(N2). Uses recursion.
- Mergesort
It separates the array always in half. It is parallelizable. Uses recursion.
* Stable Sorting
Sub O(N Log N):
- Countingsort
Only works if the items are integers in a relatively small range. The ideia is
to count the number of items in the array that have each value. O(N + M).
- Bucketsort
It devides the items in buckets and call it recursively or uses another algorithm
to sort each bucket and then concatenates the bucket's contents back into the
original array. O(N + M).
