1. Choose a sorting algorithm--either one discussed today or another one that is known to you (you might consider quicksort as a practical choice (It is discussed in the Numerical Recipes books--see the links page for links to the electronic version). Please provide a brief description of your algorithm including a discussion of the cost (i.e., the efficiency). A worst case analysis is sufficient.

Implement the algorithm in the language of your choice. (Hint: My choice would be Matlab).

2. Now consider the following problem: We want to take an ordered list and shuffle it into a random order. You should do this in such a way that each random order is equally likely. (Hint: Model "Selection sort" operating in reverse).

You may take as a given a subroutine that outputs a random number, uniformly distributed between 0 and 1.

In both MATLAB and Maple this is called "rand" (check help on "rand" in each case). The Numerical Recipes books talk about FORTRAN and C.

Assume that the cost of each run of the "rand" subroutine is a fixed constant K.  Also assume that each exchange, arithmetic operation, comparison, etc., has a fixed constant cost.

Implement your algorithm and analize its efficiency.