So stooge sort is kind of interesting. The insight is that you can sort a list by
1. sorting the first two third
2. sorting the last two third
3. sorting the first two third
Why? Well, doing (1) doesn't guarantee that the first two third of the full list are now correct, but it does guarantee that none of the elements now in the first third actually belong into the last third. And that means that all elements which belong into the last third are in the last two thirds, hence step (2) guarantees that the last third of the list is correct! And when the last third is correct, you need only sort the first two third, and the full list is correct.
after #0: 8 2 9 1 7 5 4 3 6
after #1: 1 2 5 7 8 9 4 3 6 (( 125 not in the final third! ))
after #2: 1 2 5 3 4 6 7 8 9 (( 789 is correct! ))
after #3: 1 2 3 4 5 6 7 8 9 ((
))