Is it possible to sort an array with n/2 1's and n/2 2's in 2n/3 comparisons?
Printable View
Is it possible to sort an array with n/2 1's and n/2 2's in 2n/3 comparisons?
Why do you ask and what have you worked out so far?
If you *KNOW* there are exactly n/2 1's and n/2 2's, then why sort ?
Go over the array and assign 1 to the first n/2 elements and 2 for the rest.
Exactly n assignments and no need for comparison...
Regards,
Zachm
Hi
if you mean it theoretical, if it is possible to describe an array out of n/2 1's and n/2 0's with 2n/3 bits of Information (2n/3 decisions), then the answer is "no", because n over n/2 is always greater than 2^(2n/3).
Greetings, Marco