A Sorting Puzzle

by JS

Maybe I’m underthinking the puzzle here, but it seems like heap sort solves the problem. It’s certainly meets the time requirements, but I wonder about the space issue. Does the array representation of a binary heap require a log number of pointers?

More importantly, if this was my answer, would I get a job at Google?

UPDATE: I don’t know the linear time solution, but I feel like if I could grok smoothsort I could figure it out.