Thanks, that helped!
I think that the fact that you musn't modify given array should be mentioned in the description though, since technically my previous version did work. I'm inexperienced, like probably many people here, so if we're to learn, some obvious things should be said explicitly :)

You're not meant to modify the original array. It's bad practise to modify it because it will change it permenantly and you can't reverse the process.

You're not meant to modify the original array. It's bad practise to modify it because it will change it permenantly and you can't reverse the process. Here is an example:

Neither Python nor js random tests seem to work for me when the algorithm seems good :(

I couldn't get it to work in either Python or JavaScript, screens in next comment because of spoiler policy