# 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]); list[$i]="$(list[$j])"; 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
}