# # $Id: qsort.icn,v 1.2 2004/02/12 17:07:56 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) /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