# Sort global array, $list, starting from $1 to up to $2. 0 is 
# returned if everything went okay, and nonzero if there was an error.

# We use the recursive quicksort of Tony Hoare with inline array
# swapping to partition the array. The partition item is the middle
# array item. String comparison is used.  The sort is not stable.

proc sort_list {
  sh-expr '$# != 2)'&& return 1
  typeset -i left=$1
  sh-expr 'left < 0)'|| sh-expr ' 0 == ${#list[@]})'&& return 2
  typeset -i right=$2
  sh-expr 'right >= ${#list[@]})'&& return 3
  typeset -i i=$left; typeset -i j=$right
  typeset -i mid; sh-expr 'mid= (left+right) / 2'
  typeset partition_item; setglobal partition_item = $(list[$mid])
  typeset temp
  while sh-expr 'j > i)' {
      setglobal item = $(list[i]) {
	  sh-expr 'i++'
      } {
	  sh-expr 'j--'
      }
      if sh-expr 'i <= j)' {
	  setglobal temp = $(list[$i]); compat array-assign list '$i' $(list[$j]); compat array-assign list '$j' $temp
          sh-expr 'i++'
          sh-expr 'j--'
      }
  }
  sh-expr 'left < j)'&& sort_list $left  $j  
  sh-expr 'right > i)'&& sort_list $i $right
  return 0
}

if [[ $0 == *sorting.sh ]]  { 
    [[ -n $ZSH_VERSION ]] && setopt ksharrays
    typeset -a list
    setglobal list = ''()
    sort_list -1 0 
    typeset -p list
    setglobal list = ''('one')
    typeset -p list
    sort_list 0 0 
    typeset -p list
    setglobal list = ''('one' 'two' 'three')
    sort_list 0 2
    typeset -p list
    setglobal list = ''(4 3 2 1)
    sort_list 0 3
    typeset -p list
}