Sorting and Efficiency

There are many kinds of sorting algorithm. And what I want to talk here is about there efficiency and why it has such efficiency.

Firstly, among those sorting algorithms, there are two kind of sort. One is comparison sort and another is non-comparison sort. Comparison sort means that we have to compare the item we get with another item, then we can decide where to put this item in the list. However, as for efficiency aspect, the time complexity of the most efficient comparison sort must bigger than O(n). Because we have to access to every element in the list otherwise we can no compare it with others. So if we want to compare we have to get the item's value and then the time complexity must be bigger than O(n). Non-comparison sort can have O(n) time complexity but it will demand more space to store the data.

The most intuitive algorithms of sorting might be the insertion sort. Given 1 0 4 2 as the input list, the way we think is just the process of insertion sort. We first put 0 to the front of 1 and then we find 2 is smaller than 4 but bigger than 1 then we put 2 between these two numbers. We compare the number and we put it in the right place. The time complexity of insertion sort is O(n^2). Because we have to compare the item we get in our hand with each item in front of the current item.
Selection sort is quiet simple as well. It select the first smallest item in the list and put it on the first place in the list,(or the last one, depends on the list is descending or ascending). And then the second smallest one should be put on the second place in the list. The time complexity of this algorithm is O(n^2) as well, for we have to compare the item we got with all other items.
Then here we come the QuickSort and MergeSort. These two has really good sorting algorithms. The average runtimes are all O(nlogn). Both of them are recursive.
Why they have O(nlogn) time complexity?
We can solve this buy drawing a tree.
Take MergeSort for an example
n                ------ need n step to merge
n/2 n/2          ------ each item need n/2 to merge, sum is 2*n/2 = n
n/4 n/4 n/4 n/4  ------ each item need n/4 to merge, sum is 4*n/4 = n
.......
As we can see in the above tree, each depth of the tree need n step to complete its task. Then the sum of all is nlogn because depth of the tree we can have is at most logn.

The non-comparison sorts are really interesting. But I still don't understand many of them.