# 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 {
  (($# != 2)) && return 1
  typeset -i left=$1
  ((left < 0)) || (( 0 == ${#list[@]})) && return 2
  typeset -i right=$2
  ((right >= ${#list[@]})) && return 3
  typeset -i i=$left; typeset -i j=$right
  typeset -i mid; ((mid= (left+right) / 2))
  typeset partition_item; setvar partition_item = "${list[$mid]}"
  typeset temp {
      setvar item = ${list[i]} {
	  ((i++))
      } {
	  ((j--))
      }
      if ((i <= j))  {
	  setvar temp = "${list[$i]}"; setvar list[$i]="${list[$j]}"; setvar list[$j]="$temp"
          ((i++))
          ((j--))
      }
  }
  ((left < j))  && sort_list $left  $j  
  ((right > i)) && sort_list $i $right
  return 0
}

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