parallel actually makes no reservations about making output come in order. It just so happens that jobs are typically small enough and evenly split in cpu time to come out in order. You notice it more when you have a lot of jobs running or their task duration differs a lot.
parallel will only run the same amount of jobs as your CPU has cores. On most laptops and desktops that's 2-4 which means it's only running a couple of jobs at a time. You can increase that with -j.
Here's an example to demonstrate job order does not output in the order it was submitted.
seq 20 | parallel -j 20 'sleep $[RANDOM % 20]; echo '
output on my system was (yours will likely be different)
seq 20 is a command that will output numbers 1-20. I pipe that to parallel and then tell it to run 20 simultaneous jobs to make sure they all start at the same time.
'sleep $[\[RANDOM] % 20]; is using sleep plus a zsh parameter that will return a random number between 1 and 20. Each job will sleep this random amount and then
echo. Once the job echos you'll immediately get the output from parallel.
You could also do something similar with
parallel --shuf which will shuffle the job order.