This is to sort the cards first into black v. red, then the black cards into spades v. clubs, then the spades into high v. low, then finally sort the low ones by inspection (a kind of insertion sort I guess), sort the high ones by inspection, sort the clubs similarly, etc.

Like most quicksorts, this definitely uses O(log(n)) space as you have a deck of reds, a deck of clubs, and a deck of high spades while you're handling the low spades...