This is an animation of the parallel quick sort algorithm. There are six CPUs available and one initial partition of random positive numbers to sort. The left-most circle is chosen as the pivot point of the partition. The circles less than the pivot are swept to the lower left quadrant of the partition and the circles larger than the pivot are swept to the upper right quadrant of the partition. Then the pivot circle is moved to the middle of the partition and changed to solid black. This leaves two new partitions to which the algorithm is applied recursively by any two available CPUs. The circles in a partition take on the solid color of the CPU working on them, except the pivot, which is outline.

private static void quickSort(int worker, int left, int right) {
   int pivot = nums[left]; int l = left, r = right;
   // enclose what this worker is working on in a black outline rectangle
   int ymin = minn(nums, left, right);
   int ymax = maxx(nums, left, right);
   float xpos, ypos, xsize, ysize;
   xpos = scaleX(left); ypos = scaleY(ymin);
   xsize = scaleX(right-left); ysize = scaleY(ymax-ymin);
   xa.rectangle("rect"+worker, xpos, ypos, xsize, ysize, Color.black, xa.OUTLINE);
   xa.delay(1);
   // change items sorted to this worker's color
   for (int i = left; i <= right; i++) {
      xa.color("nums"+i, colors[worker]);   // would be better to do
      xa.fill("nums"+i, xa.SOLID);          // these as a batch i.e.
   }                                        // no frameDelay
   xa.delay(1);
   // make pivot outline color
   xa.fill("nums"+left, xa.OUTLINE);
   // draw a black horizontal line from the pivot across the rectangle
   xpos = scaleX(left); ypos = scaleY(pivot);
   xsize = scaleX(right-left); ysize = 0.0f;
   xa.line("lineH"+worker, xpos, ypos, xsize, ysize, Color.black, xa.THIN);
   // draw two vertical lines at left+1 and right
   xpos = scaleX(l+1); ypos = scaleY(pivot);
   xsize = 0.0f; ysize = scaleY(ymax-pivot);
   xa.line("lineVL"+worker, xpos, ypos, xsize, ysize, Color.black, xa.THIN);
   xpos = scaleX(r); ypos = scaleY(ymin);
   xsize = 0.0f; ysize = scaleY(pivot-ymin);
   xa.line("lineVR"+worker, xpos, ypos, xsize, ysize, Color.black, xa.THIN);
   xa.delay(1);
   boolean done = false;
   while (!done) {
      if (nums[l+1] > pivot) {
         while (r > l+1 && nums[r] > pivot) { r--;
            // move the right vertical line one to the left
            if (!done) {
               xa.jumpRelative("lineVR"+worker, scaleX(-1), 0.0f);
            }
         }
         if (r > l+1) { l++;
            int temp = nums[r]; nums[r] = nums[l]; nums[l] = temp;
            done = l >= r-1;
            // swap locations and ids of the objects
            xa.moveAsync("nums"+r, scaleX(l), scaleY(nums[l]));
            xa.move("nums"+l, scaleX(r), scaleY(nums[r]));
            xa.swapIds("nums"+r, "nums"+l);
            // move the left vertical line one to the right
            if (!done) {
               xa.jumpRelative("lineVL"+worker, scaleX(1), 0.0f);
            }
         } else done = true;
      } else { l++; done = l >= r;
         // move the left vertical line one to the right
         if (!done) {
            xa.jumpRelative("lineVL"+worker, scaleX(1), 0.0f);
         }
      }
   }
   int temp = nums[left]; nums[left] = nums[l]; nums[l] = temp;
   // swap locations and ids of the objects
   xa.moveAsync("nums"+left, scaleX(l), scaleY(nums[l]));
   xa.move("nums"+l, scaleX(left), scaleY(nums[left]));
   xa.swapIds("nums"+left, "nums"+l);
   if (right-(l+1) > 0) send(task, new Task(l+1, right));
   else if (right-(l+1) == 0) {  V(doneCount);
      // color the object solid black to indicate it is in final position
      xa.color("nums"+right, Color.black);
      xa.fill("nums"+right, xa.SOLID);
   }
   // delete the line and rectangle objects
   xa.delete("rect"+worker);
   xa.delete("lineH"+worker);
   xa.delete("lineVL"+worker);
   xa.delete("lineVR"+worker);
   V(doneCount);
   // color the object solid black to indicate it is in final position
   xa.color("nums"+l, Color.black);
   xa.fill("nums"+l, xa.SOLID);
   if ((l-1)-left > 0) send(task, new Task(left, l-1));
   else if ((l-1)-left == 0) {  V(doneCount);
      // color the object solid black to indicate it is in final position
      xa.color("nums"+left, Color.black);
      xa.fill("nums"+left, xa.SOLID);
   }
}

-n: number of numbers to sort
-r: range of random numbers generated to sort (from 1)
-p: number of CPUs (worker threads) available

© 1998 Stephen J. Hartley