sort.sh

#!/bin/bash

get_col() {
    local str=$1 fs=$2 keycol=$3
    local -a a
    IFS=$fs a=($str)
    echo ${a[$keycol]}
}

cmp_str() { [[ $1 < $2 ]]; }

cmp_num() { (( $1 < $2 )); }

_insert() {
    local -i i
    for (( i=0; i < ${#lines[@]}; i++ )); do
	if $cmp_cmd $key ${keys[i]}; then
	    lines=(${lines[@]:0:i} $line ${lines[@]:i})
	    keys=(${keys[@]:0:i} $key ${keys[@]:i})
	    return
	fi
    done
    lines=(${lines[@]} $line)
    keys=(${keys[@]} $key)
}

sort_stable() {
    local fs=" " keycol=0 cmp_cmd=cmp_str opt
    while getopts nt:k: opt; do
	case $opt in
	    n) cmp_cmd=cmp_num;;
	    t) fs=$OPTARG;;
	    k) keycol=$OPTARG;;
	esac
    done
    shift $((OPTIND - 1))

    local -a lines keys
    local line key line2
    while read -r line; do
	key=$(get_col "$line" "$fs" $keycol)
	_insert
    done
    for line2 in "${lines[@]}"; do
	echo $line2
    done
}