Sort Wizard
Chris has a boring assignment, which is to sort the following numbers:
Agnishom went by and saw Chris is bored. A sorting wizard he is, he tells Chris that:
If you sort the first two third, then sort the last two third, and then sort the first two third again, the entire list of numbers will be sorted!
Curious, Chris tried it out
- sort the first two third :
- sort the last two third :
- sort the first two third :
It really sorts the entire list! Does this work for any list of length divisible by 3? Or is this just a coincidence?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Evenly divide the array into section A , B , C . Let's see what happens in each section after the sorting.
Sort the first two third
Section A , B will be sorted. Numbers that are supposed to be in C but initially lies in A will now be sorted to B . They cannot still be in A as there are no more than a section of numbers larger than numbers supposed to be in C .
Sort the last two third
Section B , C will be sorted. Numbers that are supposed to be in C was in either section B or C . Now that they are sorted, C has the right numbers and order.
Sort the first two third
Section A , B will be sorted again. Since C has already sorted, then sort A , B implies sorting the entire array!