In order to prepare a criminal case, the police has to analyze the fingerprints found in a given room. More precisely, they have to show that more than half of the fingerprints found in that room belong to the same individual (we will make a simple assumption here that the fingerprint is the same for all fingers of a person, for simplicity). You are given, in a folder, the set of fingerprints (as picture) and you are asked to identify whether it is true that more than half of those fingerprints are identical. You cannot sort the fingerprints, because you cannot clearly detect, with your own eyes, if two fingerprints are identical. Also, there is no way of ordering the fingerprints from smaller to larger. The only possible operation is to take two pictures representing two fingerprints, and put them in a specialized machine: the machine scans the two and returns whether they are identical or not. Devise an algorithm that will detect whether more than half of the fingerprints in the set are identical, using only the fingerprint comparator machine and making a maximum of O(n log n) comparisons.