Thought Process

I took a programming course in my recent semester that actually talked about an O(nlog^2(n)) algorithm to find the closest pair of points using a divide-and-conquer approach.

Here is a pdf that does a great job of explaining the approach: https://www.cs.ubc.ca/~liorma/cpsc320/files/closest-points.pdf

I upgraded the algorithm to be O(nlog(n)). I adapted the PDF's pseudocode to incorporate the changes. 

Essentially, all we do is sort P in the step where \P\ < 4, and then we can concatenate the left and right sides to get a sorted BR for free, which previously would cost us O(nlog(n))