(Quick-) sorting a list of files in POSIX sh

This code is fully POSIX-compliant, as far as I can tell. The only part that is not POSIX-compatible is the usage of pwgen for test data generation. I didn't want to go overboard on that piece, since I don't consider it part of the actual code - it's merely convenience for... testing it.

The good parts:

• it's using arrays! (Actually, it really emulates arrays in a compliant way.)
• iterative, almost in-place quicksort algorithm with random pivot selection. This is really an adapted version of greybeard's answer. The "almost" part comes from using a stack emulation to track intervals, which uses, on average, about O(log(n)) additional space, if I'm not mistaken.
• file names can include any character (but NUL, which is a common problem in POSIX shell and is often disallowed by file systems anyway).
• comparison function comp_lex_rev can easily be swapped for a different one/modified to other behavior, e.g., if you need numerical sorting in order instead - i.e., it's modular.

The ugly parts:

• rand()-based random number generation, but anything else would be difficult to do portably. My initial code used to read from /dev/urandom and parse that data, but of course, that's not part of POSIX.
• weird, function-prefixed variable names. This is a direct consequence of POSIX sh not supporting local variables. They can be emulated (to some degree) by saving old values, using variables as you see fit and finally restoring the original values, but that really makes code even more unreadable (and error-prone, as you'd either need to have one fixed exit point in functions or duplicate the restoring functionality at every possible exit point). Prefixing variables with an unique (ahem) string works around this issue, trading readability for scopeability.
• needs direct access to the global input pseudo-array. Calling the function in a subshell and not processing the result there will just be a waste of CPU time, since the original data in the parent process won't be changed. That's a general issue in shell scripting, but probably worth mentioning.
• integers are tricky. Originally, I explicitly limited the random number fetching part to 2^16 - 1, since that's the smallest guaranteed integer size - which probably means that the shell must support it too, as a minimum. However, enforcing a limit there doesn't make sense. Instead, I opted for some sort of overflow detection while generating the input array. Just keep in mind that the maximum integer size usable in the shell is implementation-specific with a hard lower bound.
• being shell-based, it's pretty slow compared to a direct binary implementation in, e.g., C. expr is notorious for being slow and forking out to other programs makes a shell script even slower. As an anecdote, I was able to cut down on the processing time in a zsh script considerably by replacing grep and sed calls with zsh-internal regular expression handling. Likewise, this point is more a general issue with shell scripting and has nothing to do with my code, but it's also good to keep it in mind.

#!/bin/sh

#set -x

comp_lex_rev () {
  comp_lex_rev_a="${1:?'No lhs passed to comp_lex_rev(), this is invalid.'}"
  comp_lex_rev_b="${2:?'No rhs passed to comp_lex_rev(), this is invalid.'}"

  comp_lex_rev_expr_out="$('expr' "x${comp_lex_rev_a}" '>' "x${comp_lex_rev_b}")"
  if [ '1' -eq "${comp_lex_rev_expr_out}" ]; then
    return '0'
  else
    return '1'
  fi
}

get_rand () {
  get_rand_min="${1:?'No minimum value passed to get_rand(), this is invalid.'}"
  get_rand_max="${2:?'No maximum value passed to get_rand(), this is invalid.'}"

  # Minimum value must be positive.
  if [ '0' -gt "${get_rand_min}" ]; then
    return '1'
  fi

  # Max > min doesn't make sense... (we could just swap them here, but meh.)
  if [ "${get_rand_min}" -gt "${get_rand_max}" ]; then
    return '1'
  fi

  # Not much to do if both are the same value.
  if [ "${get_rand_min}" -eq "${get_rand_max}" ]; then
    'printf' '%s\n' "${get_rand_min}"
    return '0'
  fi

  # Just be extra careful.
  get_rand_out=''
  while [ -z "${get_rand_out}" ] || [ "${get_rand_min}" -gt "${get_rand_out}" ] || [ "${get_rand_max}" -lt "${get_rand_out}" ]; do
    get_rand_out="$('awk' '
      BEGIN {
        srand ();
        printf ("%u", (rand () * (('"${get_rand_max}"' - '"${get_rand_min}"') + 1)) + '"${get_rand_min}"');
      }')"
  done

  'printf' '%s\n' "${get_rand_out}"
}

qsort () {
  qsort_arr="${1:?'No array base passed to qsort(), this is invalid.'}"
  qsort_n="${2:?'No array length passed to qsort(), this is invalid.'}"

  if [ '2' -gt "${qsort_n}" ]; then
    # One or zero elements are always sorted.
    return '0'
  fi

  qsort_range_0='0'
  qsort_range_1="$((${qsort_n} - 1))"
  qsort_range_n='2'
  # Must have at least one pair entry in the range "stack".
  while [ '1' -lt "${qsort_range_n}" ]; do
    qsort_range_n="$((${qsort_range_n} - 1))"
    eval 'qsort_high="${qsort_range_'"${qsort_range_n}"'}"'
    qsort_range_n="$((${qsort_range_n} - 1))"
    eval 'qsort_low="${qsort_range_'"${qsort_range_n}"'}"'

    qsort_cur_i="${qsort_low}"
    qsort_pivot_i="$('get_rand' "${qsort_low}" "${qsort_high}")"
    if [ '0' -ne "${?}" ]; then
      # Fetching random value failed, fall back to rightmost element.
      qsort_pivot_i="${qsort_high}"
    fi

    eval 'qsort_pivot="${'"${qsort_arr}"'_'"${qsort_pivot_i}"'}"'

    # Move pivot up if it isn't already.
    if [ "${qsort_high}" != "${qsort_pivot_i}" ]; then
      eval "${qsort_arr}"'_'"${qsort_pivot_i}"'="${'"${qsort_arr}"'_'"${qsort_high}"'}"'
      eval "${qsort_arr}"'_'"${qsort_high}"'="${qsort_pivot}"'
      qsort_pivot_i="${qsort_high}"
    fi

    eval 'qsort_cur="${'"${qsort_arr}"'_'"${qsort_cur_i}"'}"'
    while [ "${qsort_pivot_i}" -gt "${qsort_cur_i}" ]; do
      if 'comp_lex_rev' "${qsort_cur}" "${qsort_pivot}"; then
        qsort_cur_i="$((${qsort_cur_i} + 1))"
        eval 'qsort_cur="${'"${qsort_arr}"'_'"${qsort_cur_i}"'}"'
      else
        eval "${qsort_arr}"'_'"${qsort_pivot_i}"'="${qsort_cur}"'
        qsort_pivot_i="$((${qsort_pivot_i} - 1))"
        eval "${qsort_arr}"'_'"${qsort_cur_i}"'="${'"${qsort_arr}"'_'"${qsort_pivot_i}"'}"'
        eval 'qsort_cur="${'"${qsort_arr}"'_'"${qsort_pivot_i}"'}"'
      fi
    done
    eval "${qsort_arr}"'_'"${qsort_pivot_i}"'="${qsort_pivot}"'

    qsort_lhs_size="$((${qsort_pivot_i} - ${qsort_low}))"
    qsort_rhs_size="$((${qsort_high} - ${qsort_pivot_i}))"
    if [ "${qsort_lhs_size}" -le "${qsort_rhs_size}" ]; then
      if [ '1' -lt "${qsort_lhs_size}" ]; then
        eval 'qsort_range_'"${qsort_range_n}"'="$((${qsort_pivot_i} + 1))"'
        qsort_range_n="$((${qsort_range_n} + 1))"
        eval 'qsort_range_'"${qsort_range_n}"'="${qsort_high}"'
        qsort_range_n="$((${qsort_range_n} + 1))"

        eval 'qsort_range_'"${qsort_range_n}"'="${qsort_low}"'
        qsort_range_n="$((${qsort_range_n} + 1))"
        eval 'qsort_range_'"${qsort_range_n}"'="$((${qsort_pivot_i} - 1))"'
        qsort_range_n="$((${qsort_range_n} + 1))"
      fi
    else
      eval 'qsort_range_'"${qsort_range_n}"'="${qsort_low}"'
      qsort_range_n="$((${qsort_range_n} + 1))"
      eval 'qsort_range_'"${qsort_range_n}"'="$((${qsort_pivot_i} - 1))"'
      qsort_range_n="$((${qsort_range_n} + 1))"
    fi

    if [ '1' -lt "${qsort_rhs_size}" ]; then
      eval 'qsort_range_'"${qsort_range_n}"'="$((${qsort_pivot_i} + 1))"'
      qsort_range_n="$((${qsort_range_n} + 1))"
      eval 'qsort_range_'"${qsort_range_n}"'="${qsort_high}"'
      qsort_range_n="$((${qsort_range_n} + 1))"
    fi
  done
}

print_arr () {
  print_arr_arr="${1:?'No array base passed to print_arr(), this is invalid.'}"
  print_arr_n="${2:?'No array length passed to print_arr(), this is invalid.'}"

  print_arr_i='0'
  while [ "${print_arr_n}" -gt "${print_arr_i}" ]; do
    if [ '0' -ne "${print_arr_i}" ]; then
      'printf' '===\n'
    fi
    eval "'"'printf'"'"' '"'"'%s\n'"'"' "${'"${print_arr_arr}"'_'"${print_arr_i}"'}"'
    print_arr_i="$((${print_arr_i} + 1))"
  done
}

generate_testdata () {
  generate_testdata_dir="${1:?'No testdata directory passed to generate_testdata(), this is invalid.'}"

  generate_testdata_i='0'
  generate_testdata_n='100'
  (
    'mkdir' "${generate_testdata_dir}"
    'cd' "${generate_testdata_dir}"
    while [ "${generate_testdata_n}" -gt "${generate_testdata_i}" ]; do
      # We'll map the first underscore character to a space character and
      # ditto for right curly bracket vs. newline since pwgen generates no
      # such characters by default.
      ':' > "$('pwgen' '-s' '-y' '-c' '-n' '-r' '/' '100' '1' | 'sed' '-e' 's#_# #' '-e' 's#}#\
#')"
      generate_testdata_i="$((${generate_testdata_i} + 1))"
    done
  )
}

main () {
  main_testdir='testdata'
  if [ ! -d "${main_testdir}" ]; then
    'generate_testdata' "${main_testdir}"
  fi

  main_cur_file=''
  main_flist_n='0'
  main_flist_old_n="${main_flist_n}"
  for main_cur_file in "${main_testdir}"/*; do
    if [ -f "${main_cur_file}" ]; then
      eval 'main_flist_'"${main_flist_n}"'="${main_cur_file}"'
      main_flist_n="$((${main_flist_n} + 1))"

      if [ "${main_flist_old_n}" -ge "${main_flist_n}" ]; then
        # Overflow (or... none-flow?), stop working.
        'printf' 'Too many files to handle, aborting.\n' >&'2'
        return '1'
      else
        main_flist_old_n="${main_flist_n}"
      fi
    fi
  done

  # Sort, in reverse order.
  'qsort' 'main_flist' "${main_flist_n}"

  # And finally print out.
  'print_arr' 'main_flist' "${main_flist_n}"

  # In GNU terms,
  # 'find' "${main_testdir}" '-type' 'f' '-print0' | 'sort' '-rz' | 'sed' '-e' 's#\x0#\n===\n#g'
  # should return about the same data, only with an additional separator at the end.
}

# Actual main code.
'main'

So the idea is to process a set of files in lexicographical reverse order. As you know, you cannot parse ls, due to the weird filenames. Since this is POSIX, we don't have arrays. So here is a solution that might work.

Glob expressions return a list of possible filenames in lexicographical order. So you could do something like

for file in /path/to/dir/*; do
    [ -e "${file}" ] || continue
    some_command "${file}"
done

If you want to reverse it, you can just do:

set -- /path/to/dir/*
i=$#
while [ "$i" -gt 0 ]; do 
    eval "file=\${${i}}"; i=$((i-1));
    [ -e "${file}" ] || continue
    some_command "$file"
done

Note: we have to use an evil eval for the evaluation of the positional variable.

Update: it is possible that positional variables are already in use. In this case you can do the following:

j=$#
set -- /path/to/dir/* "$@"
i=$(($#-$j))
while [ "$i" -gt 0 ]; do 
    eval "file=\${${i}}"; i=$((i-1));
    [ -e "${file}" ] || continue
    some_command "$file"
done
shift "$i"