N log n is the very best it could get

Unreal Courses Talk
,
1

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