N log n is the very best it could get

[Christopher_Doyle]

n log n is the best you can get assuming the the first pair checked happens to be a duplicate.