Updated complementary exercises of sorting for CLRS 20110513

I finished both linear search and binary search implementation. Without saying, all the exercises in section 2.3 is a breeze.  So I am heading to the P exercises.  Here is the piled-deeper and higher Read 3 complementary material.

Insertion sort:

-C, perl, python (done)

-sentinel version of straight insertion sort (done)

-binary search (done)

-binary insertion sort (done pseudo code, put it on paper)

-recursive version of insertion sort
-C++,java, lisp, ASM
-performance, worst case, average case
-different ways to avoid -INT_MAX as the sentinel. (state of art?)
-non-adaptive version of insertion sort.
-shell sort
-library sort
-tree sort(?)
-TAOCP Exercise in 5.2.1
-Sedgewick 6.3
-Sedgewick 6.3 Exercise

Selection sort:
-C, perl, python (done)
-C++,java, lisp, ASM
-stable version of selection sort.
-bidirectional version of selection sort.
-comparison with insertion sort.
-comparison with bubble sort
-recursive version of insertion sort
-cycle sort
-heap sort variants
     -tournament sort
     -smoothsort.
-TAOCP Exercise in 5.2.3
-Sedgewick 6.2
-Sedgewick 6.2 Exercise

Merge sort:
-C, perl(done)
-python, C++,java, lisp, ASM
-performance, worst case, average case 
-Improvements from Sedgewick.
-Non-recursive version or Bottom up version 
-in place mergesort.
-no extra memory implementation (state of art?)

-variations of merge sort.
-TAOCP Exercise in 5.4
-Sedgewick 8 (read - done)
-Sedgewick 8 Exercises.
-Shene's 5-9 Exercises. 

Linear search:

-C, MIXAL (done)
-perl, python, C++,java, lisp, ASM

-TAOCP 6.1 and exercises.  Remember, it's not as trivial as you may think. 

Binary search: 

-C (done)
-perl, python, C++,java, lisp, ASM

-At least 100 problems which applies binary search.

   -TopCoder's exercises on binary search. 

   -Implement CLRS 2.3-7.

   -Shene Chapter 4. 

-After reading Gries, make sure you prove your own binary search is correct. 

-TAOCP 6.2 and exercies. 

-Chapter 4 and 5 of Programming Pearls.

-Sedgewick 12.4

-Fibonacci search

-Range search

-Variations of binary search. 

-Thinking: variations of binary search.  They produce different lo, up bounds. Interesting. 

-Thinking: can we combine the idea of distribution in binary search?

-Thinking: what happens if binary search is applied to a sequence with N inversions?