/*
 * Quicksort by Quintin Stone
 * Version 1.0
 * The quicksort algorithm for TADS 2.  Uses global to store the list
 * being sorted.  Public domain.
 */

quicksort: function(list) {
    global.quicksortlist := list;
    global.doquicksort;
    return global.quicksortlist;
    global.quicksortlist := [];
}

modify global
    partition(start, end) = {
        local pivot, bottom, top, done;
        // Partition around the last value
        pivot := self.quicksortlist[end];
        // Start outside the area to be partitioned
        bottom := start-1;
        top := end;
    
        done := nil;
        // Until all elements are partitioned...
        while (!done) {
            // Until we find an out of place element...
            while (!done) {
                // ... move the bottom up.
                bottom ++;
    
                // If we hit the top...
                if (bottom = top) {
                    // ... we are done.
                    done := true;
                    break;
                }
    
                // Is the bottom out of place?
                if (self.quicksortlist[bottom] > pivot) {
                    // Then put it at the top...
                    self.quicksortlist[top] := self.quicksortlist[bottom];
                    // ... and start searching from the top.
                    break;
                }
            }
    
            // Until we find an out of place element...
            while (!done) {
                // ... move the top down.
                top := top-1;
    
                // If we hit the bottom...
                if (top = bottom) {
                    // ... we are done.
                    done := true;
                    break;
                }
    
                // Is the top out of place?
                if (self.quicksortlist[top] < pivot) {
                    // Then put it at the bottom...
                    self.quicksortlist[bottom] := self.quicksortlist[top];
                    // ...and start searching from the bottom.
                    break;
                }
            }
        }
        // Put the pivot in its place.
        self.quicksortlist[top] := pivot;
        // Return the split point
        return top;
    }
    subquicksort(start, end) = {
        local split;
        // If there are two or more elements...
        if (start < end) {
            // ... partition the sublist...
            split := self.partition(start, end);
            // ... and sort both halves.
            self.subquicksort(start, split-1);
            self.subquicksort(split+1, end);
        } else {
            return;
        }
    }
    doquicksort() = {
        self.subquicksort(1, length(self.quicksortlist));
    }
;