sort 4 elements with 3 comparisons (not a homework question)

[Mihail121]

Now I've had a friend over telling me one could sort 4 elements (balls for ex.) using 3 measurments with a standard scale. I tried and tried and TRIED but I just can't do it. Does anyone have an idea how would it be possible?

[Nils Pipenbrinck]

It's not possible. The minimum number of compare and swap-operations you need is five (assuming the data is not already partly sorted).

[Sol_HSA]

Depends on how you define measurements. spaghetti sort (http://en.wikipedia.org/wiki/Spaghetti_sort) could definitely do it.. =)