bash-pure, 295 bytes

Result

AC

Code [DL]

a=()
while read -n 1 c; do
a+=($c)
done
q(){
local k i s=() l=()
p=()
(($#==0))&&return 0
k=$1
shift
for i; do
if [[ $i < $k ]]; then
s+=("$i")
else
l+=("$i")
fi
done
q "${s[@]}"
s=("${p[@]}")
q "${l[@]}"
l=("${p[@]}")
p=("${s[@]}" "$k" "${l[@]}")
}
q "${a[@]}"
b=$(IFS=;echo "${p[*]}")
echo $b

stdin

5955251344421047346650305269116282485247290335932758373711403263026024137221237063154884248786969290

stdout

0000000001111111112222222222222222333333333333344444444444455555555556666666667777777788888889999999

stderr

/bin/bash: warning: setlocale: LC_ALL: cannot change locale (en_US.UTF-8)

strace