# How do you write a linearithmic algorithmn?

Write psuedocode to determine the number of pairs of values in an input file that are equal. If your first try is quadratic, think again and develop a linearithmic solution.

I found this question in a textbook and I'm not sure how to write this algorithm. My guess at first was to write it along the formula nC2 = (n(n+1))/2. Any help is appreciated.

-
Hint: what changes if you sort the values before? What is the running time order for sorting? Can you even do better utilizing a dictionary? – Doc Brown Sep 26 '12 at 6:21
Its a confusingly worded question, is it asking for you to spot when a value is in a file twice, or is it asking you to spot pairs whose value match (so spotting if file has 109 and 2, but also 106 and 5)? – colinjack Jul 23 '13 at 14:36

I don't want to give you the code but some hints. The first thing to pay attention is that the exercise is asking for a linearithmic solutions. This means that you algorithm may consume N log (N) time to execute where N is the number of entries (values in the file in your case).

So the basic structure of the algorithm needed seems to be one loop through all the entries and one binary search inside the loop. To do a binary search you need an ordered entry, so order it. At the end you algorithm may look something like:

1. Order the file
2. Loop through the file
3. Binary read the file during the loop
4. Check the current value in the loop and the result of the binary search
-