;; shellsort
;; "lessp" is "<"
define vector-sort!(vec lessp)
  ;; this generates Tokuda sequence: h[n] := trunc(h[n-1] * 2.25 + 1)
  define tseq(n)
    define head cons(1 #nil)
    iterate
      repeat {car(head) < n}
        {head := cons({bit-shl(car(head)) + bit-shr(car(head) 2) + 1} head)}
      (else)
    head
  ;;
  ;; shellsort iteration
  define sort1(vec lessp step)
    define p
    define j
    define vlen vector-length(vec)
    define i step
    ;printf "sort1: step=%s\n" step
    while {i < vlen}
      {p := vector-ref(vec i)}
      {j := i}
      while {{j >= step} and lessp(p vector-ref(vec {j - step}))}
        vector-set!(vec j vector-ref(vec {j - step}))
        dec! j step
      vector-set!(vec j p)
      inc! i
  ;;
  ;; shellsort main loop
  if {vector-length(vec) > 1}
    begin
      define steps tseq(vector-length(vec))
      while {pair? steps}
        sort1(vec lessp car(steps))
        {steps := cdr(steps)}
  vec
