Sorting Algorithms

It is only for reviewing, not for learning.
-----------------------------------------------
-----------------------------------------------
Algorithm 0: Sorting Lower Bounds
-----------------------------------------------
-----------------------------------------------

The hight of the tree is log(n^2) = n * log(n)

-----------------------------------------------
-----------------------------------------------
Algorithm 1: Insertion Sort
-----------------------------------------------
-----------------------------------------------
For the i th value, swap it with its previous until the previous is smaller than it.
* Best: O(n)
* Average/Worst: O(n^2)
* Space: O(1)
* Stable and Online
* Idea:

-----------------------------------------------
-----------------------------------------------
Algorithm 2: Merge Sort
-----------------------------------------------
-----------------------------------------------
1: Divide and Conquer
2: Recursive Algorithm
3: Bottom-Up Sorting
4: Best/Average/Worst: O(nlog(n))
5: Space: O(n) for merging
6: Stable
7: can use for external sorting
Idea:

 










And the key is in merge:

-----------------------------------------------
-----------------------------------------------
Algorithm 3: Quick Sort (Straightforward Version)
-----------------------------------------------
-----------------------------------------------
1: Divide and Conquer
2: Recursive Algorithm
3: Top-Down Sorting
4: Best/Average: O(nlog(n))
5: Worst: O(n^2) (sort a reverse ordered list)
6: Space: O(log n)
7: Not Stable
Idea:

Pseudo-Code

-----------------------------------------------
-----------------------------------------------
Algorithm 5: Heap Sort
-----------------------------------------------
-----------------------------------------------
Idea:
1: Build a Maximum Heap;
2: Repeatedly Pick the Max Value in the Heap and Rebuild the left Maximum heap
3:Also useful for pick the Top k values.
4: Best/Average/Worst: O(nlog(n))
5:The amazing of Heap Tree is that it is always balanced.
6: Space: O(1)
7: Not Stable

father: N (root with index = 0)
then left child: N*2+1 and Right child: N*2+2;

-----------------------------------------------
-----------------------------------------------
Algorithm 6: Counting Sort
-----------------------------------------------
-----------------------------------------------
1: Comparison is not always necessary.
2: Time Complexity: O(n+k)
3: space: O(n+k)
4: Stable
5: Pseudo-Code

-----------------------------------------------
-----------------------------------------------
Algorithm 7: Radix Sort
-----------------------------------------------
-----------------------------------------------
1: Sort on the least-significant digit first with the Counting Sort.
2: Data Access is not local, thus cache performance is bad, compared to quick sort.
3: Time Complexity: O(n+k)