bash-pure, 285 bytes

Result

WA

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[@]}"
echo $(IFS=;echo "${p[*]}")

stdin

2044944808820914130753341958627938230099508769575407520999360432146417035125740234528731300558053450

stdout

stderr

/bin/bash: warning: setlocale: LC_ALL: cannot change locale (en_US.UTF-8)
/code.bash: line 25: syntax error: unexpected end of file

strace