Bash filevercmp - quicksort and version sort

gistfile1.sh

#!/bin/bash

unset LC_MESSAGES
unset LC_CTYPE
export LC_ALL=C
export LANG=C

match_suffix()
{
    [[ "$1" =~ (\.[A-Za-z~][A-Za-z0-9~]*)*$ ]] && printf -- "%s" "${BASH_REMATCH[0]}"
}

order ()
{
    [[ "$1" =~ [[:digit:]] ]] && echo "0" && return 0
    [[ "$1" == "~" ]]         && echo "-1" &&return 0
    [[ "$1" =~ [[:alpha:]] ]] && printf -- '%u' "'$1" && return 0
    c=$(printf -- '%u' "'$1")
    ((c+=256))
    echo "$c"
    return 0
}

# from gnulib/lib/filevercmp.c
# return == 0 a < b
#           1 a = b
#           2 a > b
verrevcmp()
{
    local s1="$1" s2="$2"
    local s1_pos=0 s2_pos=0
    local first_diff
    local s1_c s2_c s1_len s2_len

    # shortcuts
    [[ "$s1" == "$s2" ]] && return 1
    [[ -z "$s1" ]] && return 0
    [[ -z "$s2" ]] && return 2
    [[ "$s1" == "." ]] && return 0
    [[ "$s2" == "." ]] && return 2
    [[ "$s1" == ".." ]] && return 0
    [[ "$s2" == ".." ]] && return 2
    [[ "${s1:0:1}" == "." ]] && [[ "${s2:0:1}" != "." ]] && return 0
    [[ "${s2:0:1}" == "." ]] && [[ "${s1:0:1}" != "." ]] && return 2
    if [[ "${s2:0:1}" == "." ]] && [[ "${s1:0:1}" == "." ]]; then
        s1=${s1#?}
        s2=${s2#?}
    fi

    s1_suffix=$(match_suffix "$s1")
    s2_suffix=$(match_suffix "$s2")
    s1=${s1:0:$((${#s1}-${#s1_suffix}))}
    s2=${s2:0:$((${#s2}-${#s2_suffix}))}

    if [[ "$s1" == "$s2" ]]; then
        [[ $s1_suffix ]] && s1="${s1}${s1_suffix}"
        [[ $s2_suffix ]] && s2="${s2}${s2_suffix}"
    fi

    s1_len=${#s1}
    s2_len=${#s2}

    while ((s1_pos < s1_len)) || ((s2_pos < s2_len)); do
        first_diff=0
        while ( ((s1_pos < s1_len)) && ! [[ "${s1:$s1_pos:1}" =~ [[:digit:]] ]] ) \
                  || ( ((s2_pos < s2_len)) && ! [[ "${s2:$s2_pos:1}" =~ [[:digit:]] ]] ); do
            s1_c=0 s2_c=0;
            ((s1_pos != s1_len)) && s1_c=$(order "${s1:$s1_pos:1}")
            ((s2_pos != s2_len)) && s2_c=$(order "${s2:$s2_pos:1}")

            if [[ "$s1_c" != "$s2_c" ]]; then
                ((s1_c > s2_c)) && return 2
                return 0
            fi
            ((s1_pos++))
            ((s2_pos++))
        done
        while [[ "${s1:$s1_pos:1}" == "0" ]]; do
            ((s1_pos++))
        done
        while [[ "${s2:$s2_pos:1}" == "0" ]]; do
            ((s2_pos++))
        done
        while [[ "${s1:$s1_pos:1}" =~ [[:digit:]] ]] && [[ "${s2:$s2_pos:1}" =~ [[:digit:]] ]]; do
            (( $first_diff == 0 )) && first_diff=$((${s1:$s1_pos:1} - ${s2:$s2_pos:1}))
            ((s1_pos++))
            ((s2_pos++))
        done
        if [[ "${s1:$s1_pos:1}" =~ [[:digit:]] ]]; then
            return 2
        fi
        if [[ "${s2:$s2_pos:1}" =~ [[:digit:]] ]]; then
            return 0
        fi
        if (( $first_diff != 0 )); then
            (($first_diff > 0)) && return 2
            return 0
        fi
    done
    return 1
}

# bash quicksort
# use IFS=$'\n'
bash_qsort()
{
    local _func="$1"; shift
    local -a array=( "$@" ) l g e
    local x=

    if [ ${#array[@]} -lt 2 ]; then
        printf -- "%s\n" "${array[@]}"
        return
    fi

    local pivot="${array[0]}"

    for x in "${array[@]}"; do
        $_func "$x" "$pivot"
        _ret=$?
        if ((_ret == 0)); then
            l=( "${l[@]}" "$x" )
        elif ((_ret == 2)); then
            g=( "${g[@]}" "$x" )
        else
            e=( "${e[@]}" "$x" )
        fi
    done

    bash_qsort "$_func" "${l[@]}"
    printf -- "%s\n" "${e[@]}"
    bash_qsort "$_func" "${g[@]}"
}

export IFS=$'\n'

S_ARRAY=(
    "."
    ".."
    ".0"
    ".9"
    ".A"
    ".Z"
    ".a~"
    ".a"
    ".b~"
    ".b"
    ".z"
    ".zz~"
    ".zz"
    ".zz.~1~"
    ".zz.0"
    "0"
    "9"
    "A"
    "Z"
    "a~"
    "a"
    "a.b~"
    "a.b"
    "a.bc~"
    "a.bc"
    "b~"
    "b"
    "gcc-c++-10.fc9.tar.gz"
    "gcc-c++-10.fc9.tar.gz.~1~"
    "gcc-c++-10.fc9.tar.gz.~2~"
    "gcc-c++-10.8.12-0.7rc2.fc9.tar.bz2"
    "gcc-c++-10.8.12-0.7rc2.fc9.tar.bz2.~1~"
    "glibc-2-0.1.beta1.fc10.rpm"
    "glibc-common-5-0.2.beta2.fc9.ebuild"
    "glibc-common-5-0.2b.deb"
    "glibc-common-11b.ebuild"
    "glibc-common-11-0.6rc2.ebuild"
    "libstdc++-0.5.8.11-0.7rc2.fc10.tar.gz"
    "libstdc++-4a.fc8.tar.gz"
    "libstdc++-4.10.4.20040204svn.rpm"
    "libstdc++-devel-3.fc8.ebuild"
    "libstdc++-devel-3a.fc9.tar.gz"
    "libstdc++-devel-8.fc8.deb"
    "libstdc++-devel-8.6.2-0.4b.fc8"
    "linux-4.1.0-0.rc2.git0.1.fc23.x86_64"
    "linux-4.1.0-0.rc3.git0.1.fc23.x86_64"
    "linux-4.1.0-0.rc3.git3.2.fc23.x86_64"
    "linux-4.1.0-0.rc4.git0.1.fc23.x86_64"
    "linux-4.1.0-0.rc7.git0.1.fc23.x86_64"
    "linux-4.1.0-1.fc23.x86_64"
    "linux-4.2.0-0.rc0.git4.2.fc23.x86_64"
    "linux-4.2.0-0.rc1.git2.2.fc23.x86_64"
    "nss_ldap-1-0.2b.fc9.tar.bz2"
    "nss_ldap-1-0.6rc2.fc8.tar.gz"
    "nss_ldap-1.0-0.1a.tar.gz"
    "nss_ldap-10beta1.fc8.tar.gz"
    "nss_ldap-10.11.8.6.20040204cvs.fc10.ebuild"
    "z"
    "zz~"
    "zz"
    "zz.~1~"
    "zz.0"
    "#.b#"
)


for ((t=0; t < 10; t++)); do
    ARRAY=( $(printf "%s\n" "${S_ARRAY[@]}" | shuf) )

    echo "Before Sort:"

    printf -- "%s\n" "${ARRAY[@]}"

    echo
    time ARRAY=( $(bash_qsort verrevcmp "${ARRAY[@]}") )

    echo "After Sort: "

    printf -- "%s\n" "${ARRAY[@]}"

    for ((i=0; i<${#S_ARRAY[@]}; i++)); do
        if [[ "${S_ARRAY[$i]}" != "${ARRAY[$i]}" ]]; then
            echo "Sort failed: ${S_ARRAY[$i]} != ${ARRAY[$i]}"
            exit 1
        fi
    done

    echo "--------------------------------------------------------------"
    echo "TEST: PASSED"
    echo "--------------------------------------------------------------"
done

exit 0