#Time Complexity from O(n log(n)) to O(n^2)
#Space Complexity O(log(n))
#elements less than the middle one go left, greater go right,
#then each part is sorted the same way
quickSort() {
local -n arr=$1
local first=$2
local last=$3
if ((first >= last)); then
return
fi
local i=$first
local j=$last
local x=${arr[(first + last) / 2]}
local tmp
while ((i <= j)); do
while ((arr[i] < x)); do
((i++))
done
while ((arr[j] > x)); do
((j--))
done
if ((i <= j)); then
tmp=${arr[i]}
arr[i]=${arr[j]}
arr[j]=$tmp
((i++, j--))
fi
done
quickSort "$1" "$first" "$j"
quickSort "$1" "$i" "$last"
}
items=(4 1 5 3 2)
#the sort works in place: a copy keeps items as they are
sortItems=("${items[@]}")
quickSort sortItems 0 $((${#sortItems[@]} - 1))
#sortItems is (1 2 3 4 5)
#in practice the lines are sorted by sort -n
echo "items is (${items[*]})"
echo "sortItems is (${sortItems[*]})"