Useless Pure-Bash MergeSort

bash_only_mergesort.bash

#!/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