Algorithms and Data Structures
Excercise 9
Sort 2 (The Fastest Method)

Problem 1 ［PostScript for printing］

(1) Sort the following sequence by using merge sort. Also, write the state of sequence at all stages of the calculation process.

5 1 4 3 8 2 6 7

(2) The following code is a function which performs quick sort and comment lines. Write which comment corresponds to which portion of the program for every comment.

(3) Divide the following sequence using partition procedure equivalent to that of function (2).

5 7 3 6 2 8 1

Problem 2

Write the function which performs quick sort. A program should fulfill the following conditions:

• The number of the data is 10000.
• Data is created using a random number.
• It is not necessary to display the middle of sorting and a result.
• Use gethrtime function for the time measurement.

Problem 3

There is a mistake in the quicksort function written in the textbook. When data fulfills certain conditions, it may be unable to sort well. Consider conditions in case of which the function doesn't work well. And correct the program.