resource sorter
   op print_array(ref a[1:*] : int), sort(ref a[1:*] : int)
body sorter()
   proc print_array(a)
      fa i := 1 to ub(a) -> writes(" ", a[i]) af;  writes("\n")
   end print_array

   procedure qs(ref nums[1:*] : int; val left, right : int)  # quicksort
      if right-left <= 0 -> return fi
      var pivot := nums[left]
      var l := left, r := right

      var not_done := true
      do not_done ->
         if nums[l+1] > pivot ->  # needs to be moved to other end of nums
            do (r > l+1) and (nums[r] > pivot) -> r-- od  # find one to swap
            if r > l+1 -> l++; nums[r] :=: nums[l]; not_done := l < r-1
            [] else -> not_done := false  # if can't find one to swap, then
            fi                            # nums now partitioned; we are done
         [] else -> l++; not_done := l < r  # need not be moved to other end
         fi
      od  # when this loop finishes, nums[left] is the pivot,
          # nums[left:l] <= pivot and nums[l+1,right] > pivot
          #
                                #   [pivot, <= | > ]
                                #    ^        ^ ^ ^
                                #    |        | | |
                                # left        l r right
                                #    |        | | |
                                #    v        v v v
      nums[left] :=: nums[l]    #   [<=, pivot | > ]

         # nums[left,l-1] <= pivot, nums[l] = pivot, and nums[l+1,right] > pivot
         # if right-(l+1) = 0, nums[l+1:right] is singleton so sorted
      qs(nums, l+1, right)
         # nums[l] = pivot is singleton so sorted
      qs(nums, left, l-1)
         # if (l-1)-left = 0, nums[left:l-1] is singleton so sorted
   end qs

   proc sort(a)   # into non-decreasing order
      qs(a, 1, ub(a))
   end sort
end sorter

resource user()
   import sorter
   var sort_cap : cap sorter
   sort_cap := create sorter()
   var stat, n : int
   do true ->
      writes("number of integers to sort? ")
      stat := read(n)
      if stat = EOF -> write("no more input"); exit
      [] stat = 0   -> write("malformed input -- try again"); next
      [] n <= 0     -> write("enter a positive number"); next
      fi
      var nums[1:n] : int  #storage reallocated each time through loop
      write("input integers, separated by white space")
      fa i := 1 to n -> read(nums[i]) af
      write("original numbers");   sort_cap.print_array(nums)
      sort_cap.sort(nums)
      write("sorted numbers");     sort_cap.print_array(nums)
   od
end user

/* ............... Example compile and run(s)

% sr -o quicksort quicksort.sr
% ./quicksort
number of integers to sort? 5
input integers, separated by white space
22 -33 -11 0 1
original numbers
 22 -33 -11 0 1
sorted numbers
 -33 -11 0 1 22
number of integers to sort? abc
malformed input -- try again
number of integers to sort? -1
enter a positive number
number of integers to sort? ^D
no more input
                                              */