#
# $Id: qsort.icn,v 1.3 2006-07-10 13:44:28 rparlett Exp $
#
# This file is in the public domain.
#
# Author: Robert Parlett (parlett@dial.pipex.com)
#

package util

#
# The classic quick sort procedure.
#
procedure qsort(l, comparator, first, last)
   local i, j, pivot
   /first := 1
   /last := *l

   i := first
   j := last

   if i = j then
      return l

   pivot := l[(i + j) / 2]
   repeat {
      while comparator.compare(l[i], pivot) do i +:= 1
      while comparator.compare(pivot, l[j]) do j -:= 1
      if i <= j then {
         l[i] :=: l[j]
         i +:= 1
         j -:= 1
      }
      if i > j then
         break
   }
   if first < j then
      qsort(l, comparator, first, j)
   if i < last then
      qsort(l, comparator, i, last)
   return l
end