#!/bin/sh

set -e

usage() { echo "usage: shsort [-r] <comparator> [<list>]" >&2 && exit 0; }

[ "$1" ] || usage

[ "$1" != "-r" ] || { rev="yes" && shift; }

cmpfn="$1"
shift

quicksort() {
    len="$(printf "$@\n" | wc -l)"
    [ "$len" -gt 1 ] || { echo "$@" && return 0; }

    pvtidx="$(expr $len / 2)"
    pvt="$(printf "$@\n" | head -n$pvtidx | tail -n1)"

    parted="$(printf "$@\n" | while read elem; do
        { [ "$elem" ] && [ "$elem" != "$pvt" ]; } || continue
        [ "$($cmpfn "$elem < $pvt")" = "yes" ] \
        && printf "<\t$elem\n" \
        || printf ">\t$elem\n"
    done)"
    lesser="$(printf "$parted\n" | grep "^<" | cut -f2)"
    greater="$(printf "$parted\n" | grep "^>" | cut -f2)"

    if [ "$rev" ]; then
        printf "%s\n%s\n%s\n" "$(quicksort "$lesser")" "$pvt" "$(quicksort "$greater")"
    else
        printf "%s\n%s\n%s\n" "$(quicksort "$greater")" "$pvt" "$(quicksort "$lesser")"
    fi
}

if [ "$@" ]; then
    elems="$@"
else
    while read input; do
        elems="$elems$input\n"
    done
fi
[ "$elems" ] || usage

quicksort "$elems" | sed '/^$/d'