Now let's look at a slightly more interesting and utilitarian application of dynamic parallelism—the Quicksort Algorithm. This is actually a well-suited algorithm for parallelization, as we will see.
Let's start with a brief review. Quicksort is a recursive and in-place sorting algorithm that has an average and best case performance of O(N log N), and worst-case performance of O(N2). Quicksort is performed by choosing an arbitrary point called a pivot in an unsorted array, and then partitioning the array into a left array (which contains all points less than the pivot), a right array (which contains all points equal to or greater than the pivot), with the pivot in-between the two arrays. If one or both of ...