I was working on some programming projects then I suddenly got stuck at a particular problem that took me a whole day still unable to solve. When simplified, it looks like this:
Consider a tournament where we want to find out the ranking of N contestants. In each competition, M contestants compete with each other at the same time to generate a ranking order. How many such competitions S are required in the tournament to fully rank all contestants given M” title=”N => M”/>?
Did some search online and it turns out that this is an ongoing research problem more officially known as the K-ary sort algorithm, although the it is formulated slightly differently where (which would become regular binary sort) and .
There are a few things that are obvious:
1. Inherently at atomic level, the act of ranking involves comparing 2 contestants, which is a binary case.
2. We do not need every contestant to have had competed with every other contestant. Between 2 contestants, the winner wins every other person that the loser wins and vice versa.
3. We must have information of combination(N, 2) rankings between any 2 contestants.
To be continued…