Nim quicksort

quicksort.nim

## Swap xs[ix] and xs[iy]
proc swap[A](xs: var seq[A], ix: int, iy: int) =
  let tmp = xs[ix]
  xs[ix] = xs[iy]
  xs[iy] = tmp

## 'Pivotizes' the seq by rearranging the seq
## such that there is an index i with value vi
## so that if j < i then vj < vi and if
## j > i then vj >= vi
proc pivotize[A](xs: var seq[A], s: Slice[int]): int =
  if len(xs) >= 2:
    var pivotIx = s.a
    let pivot = xs[pivotIx]
    for i in s.a+1..s.b:
       # we got an element thats smaller and to the right of the pivot
       if (xs[i] < pivot and pivotIx < i):
         discard """ swap the current element with the element right to the pivot
          we can do this because the element right to the pivot is either
          greater than the pivot (so we can shift it even further right)
          or we haven't looked at it yet (in which case, shifting it further
          to the right causes no harm). Then we swap the pivot and the element
          right next to the pivot (which is now the current element)"""
         swap(xs, i, pivotIx+1)
         swap(xs, pivotIx, pivotIx+1)
         pivotIx = pivotIx + 1
      # Our pivot can never be to the right of an element bigger than it
      # by construction, so there is no else case
    return pivotIx

## Sorts the range in xs given by the slice using quicksort the quicksort algorithm
proc quicksort[A](xs: var seq[A], s: Slice[int]) =
  if s.b-s.a > 1:
    let pivot = pivotize(xs,s)
    quicksort(xs, s.a .. pivot)
    quicksort(xs, pivot+1 .. s.b)
## Sorts xs using the quicksort algorithm
proc quicksort[A](xs: var seq[A]) = quicksort(xs, low(xs)..high(xs))

var collection = @[6,4,8,3,1,9,7,5,2,10]
quicksort(collection)
echo(repr(collection))