Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Useless Pure-Bash MergeSort
#!/bin/bash
#############################################################################
## ##
## bash_only_mergesort.bash -- mergesort written in pure bash ##
## ##
## Why: I have no idea. This isn't going to ever be useful. ##
## Sanity: Do not use this. Ever. Just use sort(1) ##
## Author: pdkl95@thoughtnoise.net ##
## Homepage: https://gist.github.com/pdkl95 ##
## License: This nonsense is public domain. ##
## ##
## This rivals my dircolors(1) M4 macro as the most useless and insane ##
## piece of code I have ever written. ##
## ##
## An attempt has been made to make it somewhat efficient by slicing ##
## the params as a bash array during the recursive part. ##
## ##
## Any gains are immediately thrown out the window in the merge ##
## part, where shifting off the first elemenent of the arrays involves ##
## replacing the lists with a duplicate of [2..n]. Keeping the index ##
## that are incremented during the merge would be far saner, but ##
## it's not worth bothering about. ##
## ##
## You can observer the nesting if you use -s as the first parameter. ##
## ##
#############################################################################
declare show_nesting=false
declare quiet=false
while (( $# > 0 ))
do
case "$1" in
-h | --help)
echo "usage: $(basename "$0") [options] [list_of_integers...]"
echo
echo 'Mergesort demo in pure bash.'
echo
echo 'Supply a list to sort as params,'
echo 'or leave blank to use $(seq 9 | shuf)'
echo
echo 'OPTIONS'
echo ' -q, --quiet Only output the sorted list'
echo ' -s, --show-nesting Print the subshell nesting on STDERR'
exit 0
;;
-s | --show-nesting)
show_nesting=true
shift
;;
-q | --quiet)
quiet=true
shift
;;
--) shift ; break ;;
-*) echo "bad opt: $1" ; exit 1 ;;
*) break ;;
esac
done
declare -ai list
if (( $# < 1 )) ; then
list=( $(seq 9 | shuf) )
else
list=( "$@" )
fi
show() {
if $show_nesting
then
echo "$*" 1>&2
fi
}
mergesort() {
if (( $# < 2 ))
then
show "MergeSort<${BASH_SUBSHELL}> R: [$@]"
echo "$@"
return 0
fi
show "MergeSort<${BASH_SUBSHELL}> I: [$@]"
local -i a0 b0 m=$(( $# / 2 ))
local -ai a=( $(mergesort "${@:1:$m}") )
local -ai b=( $(mergesort "${@:$(( $m + 1 )):$(( $# - $m ))}") )
local -ai out=()
while true
do
# sleep 1
# echo "--" 1>&2
# declare -p a b out 1>&2
if (( ${#a[@]} < 1 ))
then
if (( ${#b[@]} < 1 ))
then # both empty
break
else # array 'a' is empty
out+=( "${b[@]}" )
break
fi
else
if (( ${#b[@]} < 1 ))
then # array 'b' is empty
out+=( "${a[@]}" )
break
else # neither is empty (must merge)
a0=${a[0]}
b0=${b[0]}
if (( a0 < b0 )) ; then
out+=( $a0 )
a=("${a[@]:1}")
else
out+=( $b0 )
b=("${b[@]:1}")
fi
fi
fi
done
show "MergeSort<${BASH_SUBSHELL}> O: [${out[@]}]"
echo "${out[@]}"
}
$show_nesting && show
declare -ai sorted=( $(mergesort "${list[@]}") )
$show_nesting && show
if $quiet
then
echo "${sorted[@]}"
else
echo "orig_list: ${list[@]}"
echo "mergesort: ${sorted[@]}"
fi
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.