🚀 go-pugleaf

On Mon, 28 Jun 1999 00:10:31 +0200, "Vincent Wolowski"
<vwolowski@t-online.de> wrote:

>Can someone tell me how to program quicksort with threads?

Quicksort works by partitioning the array of items to be sorted into
two groups, where all of the items in one group are guaranteed to sort
before all of the items in the other group. It then sets to work on
the two groups, partitioning each of them into two subgroups, and so
on. Since sorting each of a pair of groups is independent of sorting
the other member of the pair, the two groups may be sorted in separate
threads.

So the basic pseudocode (not including various optimizations) might
look something like this:

 function QuickSort(array of items)
 begin
 if array contains only one element, exit
 partition array of items into two subarrays; call them left_array
   and right_array
 start a new thread
 in the context of the new thread, QuickSort(right_array)
 in the context of the current thread, QuickSort(left_array)
 end

-Steve