#!/bin/sh
# Copyright 2005 Daniel Cer (daniel.cer@cs.colorado.edu)
#
# This work is licensed under the Creative Commons Attribution-NonCommercial-
# ShareAlike License. To view a copy of this license, visit 
# http://creativecommons.org/licenses/by-nc-sa/2.5/ or send a letter to 
# Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 
# 94105, USA.

# insetion_sort - sorts the array reference by the first argument to this 
# function.
#
# e.g. to sort an array '$entries[@]', the following statement would be
# used: insertion_sort
function insertion_sort { local entries_ref=$1; local i j value entries_N val_j
  eval entries_N=\${#$entries_ref[@]}
  for i in `seq 1 $[entries_N-1]`; do eval value=\${$entries_ref[$i]}
    for j in `seq $[i-1] -1 0`; do eval val_j=\${$entries_ref[$j]}
      if [ `bc<<<"$val_j < $value"` -eq 1 ]; then
        eval $entries_ref[$[j+1]]=$value; break
      fi
      eval $entries_ref[$[j+1]]=$val_j
      if [ $j -eq 0 ]; then eval $entries_ref[0]=$value; fi
    done
  done
}

if [ $# -ne 1 ]; then
  echo -e "Usage:\n\t$0 (file with numbers to sort)" >&2; exit -1
fi

# read in the items
exec 3<$1; while read -u 3 entry; do entries[${#entries[@]}]=$entry; done; 3>&-

# sort them
insertion_sort entries

# display the sorted results
for entry in ${entries[@]}; do echo $entry; done