Something about Heapsort

Heapsort has two pleasant properties

1. an average and worst-case O(N*LogN) complexity
2. in place algorithm, no extra space is needed.

Heapsort has two steps:

1. first make a max heap (or min heap), this operation takes O(N)
2. pop the root of the heap, swap it with the last element in the heap (the last leaf), do heapify on the elements rangeing from 1 to N-1. Basically, we build a new max (min) heap on the elements rangeing from 1 to N-1
3. repeat the step 2

About American Flag Sort

American Flag Sort is an extension of Dutch Flag Problem which divides an array into three group. American Flag Sort further divides an array into multiple buckets based on certain order. For example, 256 buckets based on ASCII value. Essentially, it is a in-place radix sort. It is favored for sorting integers and strings givens its speed and space advantage.

• The algorithm needs two passes. First scan the array, so that we know the number of the the objects that will be stored in each bucket.
• Then we know the start location of each bucket. Scan the array for the second time, put the object to the corresponding bucket and update the bucket cursor.
• If sorting strings, may need to apply the same algorithm to sort objects within each bucket.

Something about Quicksort

     1. Why the average time complexity is O(NlogN)?

• Think the whole process as a tree-like structure, in each iteration, quicksort can divide the problem in half, so the depth of the tree is logN, then in each depth level, essentially N comparison needs to be done. Therefore the average time complexity is O(NlogN).
• Use Master Theory, T(N) = 2*T(N/2) + N. Then we have T(N/2) = 2*T(N/4) + N/2. Therefore, we can derive T(N) = 4*T(N/4) + 2*N = 8*T(N/8) + 3N = .... Then eventually we can have T(N) = a*T(1) + b*N, where a = O(2^(logN)), b =O(logN). So  T(N) = O(NlogN).

   2. When is the worst case O(N^2)?

• if in each iteration, we always happen to select the smallest (or biggest, depends on how you do quicksort), then you can't effectively break the input array into two sub arrays. When you have N elements in the array, you can only get an array of size 1 and an array of size N-1. Then the cost is O(N^2). Especially when you try to sort a sorted list and you always choose the lowest index as pivot, you will always have O(N^2).