Closest Pair Algorithm in JavaScript

Question

I'm trying to implement a divide and conquer algorithm to find the closest pair of points in a randomly-generated set of points using JavaScript. This algorithm should be running in O(n log n) time, but it is taking considerably longer to run than a simple brute force algorithm, which should be O(n^2).

I've created two jsfiddles that time the algorithms for an array of 16000 points:

• Divide and Conquer
• Brute Force

My hypothesis is that the divide and conquer is so slow because JavaScript arrays are actually hash tables. Is it possible to significantly speed up the algorithm in JavaScript? If so, what would be the best way to go about doing this?

Answer 1

At a glance, your merge function is allocating way too much memory (roughly order O(n^2)). I made a hacky way to measure this here. The basic idea is I just have a counter in the global scope, and add the size of the array generated by merge each time it is called. Hopefully this is enough info for you to fix it, if you encounter any more problems I'd be happy to provide a few additional pointers.

Also, just by playing with the numbers it's pretty easy to rule out it being a hash table issue* - an algorithm slowed by hash table would not exhibit a faster growth rate than O(n log n), it would just start slow and grow along the same lines. If you try a range of values out though, it should become apparent that it's growing faster than that, suggesting a different issue.

*the internal implementation of javascript arrays is a bit more complicated than them just being objects, but for the point I'm trying to make it doesn't really matter