# Nicholas Rinard Keene's Little Bit This is quicksort implemented in perl. This implementation run on a Macbook Pro 2.4GHz Dual Core machine sorts 100,000 random integers between 1 and 1000 in about three seconds. That is reasonably quick, but compares approximately to mergesort, and performance degrades considerably if the integers have lower cardinality (a smaller overall numerical range).
`#!perluse strict;my (\$list_size, \$max_num, @numbers, \$start_time);#Generate a large number of random integers\$list_size = 100000;\$max_num = 1000;@numbers = ();for(1..\$list_size) {  push(@numbers, int(rand(\$max_num)));}#Print out the number array, then sort it, then print it out again in sorted order#print "@numbers\n";\$start_time = time;quicksort(0, \$#numbers, \@numbers);#print "@numbers\n";print "QUICKSORT sorted \$list_size random integers between 1 and \$max_num in " . (time - \$start_time) . " seconds.\n";#Quicksort works by dividing the list into two parts around an arbitrary pivot number#We arbitrarily choose the first number in the list to be the pivot#Then we simply recurse over the bottom and top parts of the list#The recursion stops when the list of the length ("right minus left") is 1sub quicksort {  my( \$left, \$right, \$quicknums ) = @_;   if( \$right > \$left ) {    my \$pivotNewIndex = partition(\$left, \$right, \$left, \$quicknums);    quicksort(\$left, \$pivotNewIndex -1, \$quicknums);    quicksort(\$pivotNewIndex + 1, \$right, \$quicknums);  }}#To partition a list around a pivot index, we put each element above or below the pivot#The result is a list which is partially sorted, in that the list as a whole has a high and low part#We do this by first moving the pivot value safely to the end of the list#Then we compare each item with the list to the pivot, moving lower values to the left in the array#Finally we put the pivot back into place between the two parts of the list and return its new indexsub partition {  my( \$left, \$right, \$pivotIndex, \$partnums ) = @_;  my (\$pivotValue, \$storeIndex);   \$pivotValue = \$partnums->[\$pivotIndex];  swap(\$pivotIndex, \$right, \$partnums);  \$storeIndex = \$left;   for( my \$i = \$left; \$i <= \$right; \$i++ ) {    if( \$partnums->[\$i] < \$pivotValue ) {      swap(\$i, \$storeIndex, \$partnums);      \$storeIndex++;    }  }      swap(\$storeIndex, \$right, \$partnums);  return \$storeIndex;}  #A swap operation takes a list reference and exchanges the values at the indicated indices #The swap operation allows quicksort to work in one list sub swap {  my( \$index1, \$index2, \$anyarray ) = @_;  \$_ = \$anyarray->[\$index1];  \$anyarray->[\$index1] = \$anyarray->[\$index2];  \$anyarray->[\$index2] = \$_;}`