sort ()
{
f=false
for x
do
if ! $f
then
set -- "$1"
f=true
else
q=false
for y
do
if $q || $cmp "$x" "$y"
then
set -- "$@" "$y"
else
set -- "$@" "$x" "$y"
q=true
fi
shift
done
$q || set -- "$@" "$x"
fi
done
$cont "$@"
}
islonger ()
{
[ ${#1} -gt ${#2} ]
}
puts ()
{
printf %s\\n "$@"
}
cmp=islonger
cont=puts
sort "$@"
sort ()
{
f=false
for x
do
if ! $f
then
set -- "$1"
f=true
else
q=false
# marginally faster than while + "$1" in my tests
for y
do
if $q || "$cmp" "$x" "$y"
then
set -- "$@" "$y"
else
set -- "$@" "$x" "$y"
q=true
fi
shift
done
$q || set -- "$@" "$x"
fi
done
"$cont" "$@"
}
islonger ()
{
[ ${#1} -gt ${#2} ]
}
puts ()
{
printf %s\\n "$@"
}
cmp=islonger
cont=puts
sort "$@"
While not a pinnacle of efficiency, on my machine bash runs it fast enough to be useful foron really small datasetsinputs:
$ shuf /usr/share/dict/words | head -n 50 | xargs -d '\n' sh -c 'time sh sort.sh "$@"'
ell
mods
Lapps
belay
astir
bushed
logins
shoals
arctic
utmost
meshed
Hooters
mousers
Chris's
potting
brawl's
egoists
stooped
minored
zaniness
augments
landline
lodger's
psychics
caftan's
rosiness
nominees
hornet's
Rockwell
wineries
fortune's
slacker's
varnished
supported
Bulgarian
Visayans's
ambiance's
Minamoto's
distress's
vocalist's
sketchiest
Proserpine
unbreakable
Kandinsky's
wrongness's
dowdiness's
castigators
childbearing
bouillabaisse
real 0m0.052s
user 0m0.048s
sys 0m0.004s
$ shuf /usr/share/dict/words | head -n 50 | xargs -d '\n' sh -c 'time sh sort.sh "$@"' sh
sic
alto
Biko
needs
Capet
scuba
bowed
sicks
waxier
Kodaly
Tuvalu
hubbub
Gide's
panache
Joann's
peeling
mermaid
wingnut
savvies
crybaby
Python's
nitwit's
junction
tailored
tussocks
rotaries
Brandi's
leafiest
banknote
Spence's
Heriberto
prepaying
telephony
indelible
addendum's
stampeding
hatchway's
pathogenic
Englishman
escarole's
outstaying
synonymous
Youngstown
rebroadcast
overstuffed
interweaves
deliquescent
grandmothers
Cryptozoic's
mammography's
real 0m0.039s
user 0m0.038s
sys 0m0.001s
Here is a merge sort using the same principles:
sort ()
{
n=1
while [ $n -lt $# ]
do
h=0
k=$n
l=$n
while [ $h -lt $# ]
do
i=0
j=0
if [ $(($# - h)) -lt $((n << 1)) ]
then
if [ $(($# - h)) -le $n ]
then
k=$(($# - h))
l=0
else
l=$(($# % n))
fi
fi
for x
do
[ $i -eq 0 ] && shift $k
while [ $j -lt $l ]
do
if [ $i -eq $k ] || "$cmp" "$x" "$1"
then
set -- "$@" "$1"
shift
j=$((j + 1))
else
break
fi
done
[ $i -eq $k ] && break
set -- "$@" "$x"
i=$((i + 1))
done
h=$((h + (n << 1)))
done
n=$((n << 1))
done
"$cont" "$@"
}
$ shuf /usr/share/dict/words | head -n 1000 | xargs -d '\n' sh -c 'time sh sort.sh "$@"' sh >/dev/null
real 0m19.918s
user 0m19.917s
sys 0m0.001s
