Is there a O(n) shuffling algorithm? In place, I don't think so.

Um, the "Knuth Shuffle" aka "Fisher-Yates" ?

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle