ThreadMentor: Visualizing Quicksort

Let us see how threads are created in order to sort 10 elements

Index 0 1 2 3 4 5 6 7 8 9
a[ ] 9 1 11 17 13 18 4 12 14 5

After the program runs on the above input for a short amount of time, we have the following Thread Status window. In addition to the main thread that is in the join state, there eight more threads, Sorting(0:9), Sorting(0:1), Sorting(0:-1), Sorting(3:9), Sorting(3:3), Sorting(1:1), Sorting(5:9) and Sorting(5:5). Of these eight, thread Sorting(0:9) is joining, threads Sorting(0:1), Sorting(3:9) and Sorting(5:9) are running, and threads Sorting(0:-1), Sorting(3:3), Sorting(1:1) and Sorting(5:5) have terminated.

The following History Graph clearly shows the running status. Because the four terminated threads handle the array sections that have no element or has only one element, they terminate immediately once they are created. As a result, the visualization system has no way to show their history bars due to their life spans are so short that are less than the minimal resolution of the history bar.

Let us see how these threads are created. See the diagram below. Please refer to the source program of quicksort. The main program creates thread Sorting(0:9) and waits for its completion by executing a thread join. After this, the main thread and thread Sorting(0:9) are both running. Then, the partition step of thread Sorting(0:9) places the pivot element 5 in a[2] and creates two threads Sorting(0:1) and Sorting(3:9) to sort the left segment a[0:1] and the right segment a[3:9]. For the left segment, it is further divided into two and handled by threads Sorting(0:-1) and Sorting(1:1). Both of these threads terminated as shown in the Thread Status and History Graph windows, and, as a result, when thread Sorting(0:1) will be executing its two joins, it will be successful. Then, thread Sorting(0:1) will terminates. The rest creations and joins are similar. As long as you trace the source program you will get the creation tree as shown below.

The following Thread Status window shows a snapshot near the end of execution. There are 11 threads created and seven of them terminated. All other threads, the main thread included, are joining with their child threads.

The following History Graph window illustrates the relative timing of termination and joining. As mentioned earlier, both child threads of thread Sorting(0:1) terminated when the first snapshot was taken. In this snapshot, we see that the history bar of thread Sorting(0:1) ends early because it is no more in the system.

The following is a complete creation tree of these 11 threads.