the problem: you have arbitrary input, which is orderable but not sort(1)able, and you want to sort it in a POSIXish shell.

more concrete and to the point: this came up after reading #529963. the upgrade facility of dbconfig-common looks in a number of directories for files which correspond to upgrade commands to issue when upgrading between specific versions of a package. i.e. you might have:

/usr/share/dbconfig-common/data/<pkg>/upgrade/mysql/5
/usr/share/dbconfig-common/data/<pkg>/upgrade/mysql/5.1
/usr/share/dbconfig-common/data/<pkg>/upgrade/mysql/5.10
/usr/share/dbconfig-common/data/<pkg>/upgrade/mysql/5.10.1
/usr/share/dbconfig-common/data/<pkg>/upgrade/mysql/5.10~pre1
/usr/share/dbconfig-common/data/<pkg>/upgrade/mysql/5.10+lenny1
/usr/share/dbconfig-common/data/<pkg>/upgrade/mysql/5.11

a find + sort would list them in exactly this order, which is not the correct order with respect to debian version ordering (and thus could lead to interesting results if these upgrade commands needed to be applied in order).

a possible workaround, as mentioned in the bug, is to /cheat/, by using fake version numbers (i.e. 5.101pre1, 5.102, 5.103_lenny1, etc), but hey, it's a lazy saturday morning so let's see if we can get a better solution

a solution:

#!/bin/sh

set -eu

compare(){
  dpkg --compare-versions $1 le $2
}

insert(){
  local item halfindex firsthalf secondhalf
  item="$1"
  shift
  if [ $# -eq 0 ]; then
    echo $item
  elif [ $# -eq 1 ]; then
    if compare $item $1; then
      echo $item $1
    else
      echo $1 $item
    fi
  else
    firsthalf=""
    halfindex=$(expr $# / 2)
    while [ $# -gt $halfindex ]; do
      firsthalf="${firsthalf:+$firsthalf }$1"
      shift
    done
    secondhalf="$@"
    if compare $item ${1:-$item}; then
      eval set -- $firsthalf
      echo $(insert $item ${@:+"$@"}) $secondhalf
    else
      echo $firsthalf $(insert $item ${@:+"$@"})
    fi
  fi
}

while read input; do
  eval set -- ${list:-}
  list=$(insert "$input" ${@:+"$@"})
done
echo $list