Our code works, but it is quite slow. The culprit is the comparator function, which is doing a lot of work. This comparator will be called many times during the course of a sort, which means that it needs to be fast.
Array sorting performance
The actual sort algorithm used by JavaScript is not defined by the standard. It may be a simple sort such as a bubble sort (worst case of Θ(n2) in computational complexity terms), or a more sophisticated approach such as a quick sort (which is Θ(n log n) on average). It is safe to say, though, that doubling the number of items in an array will more than double the number of times the comparator function is called.
The actual sort algorithm used by JavaScript is not defined by the standard. It may be a simple sort such as a bubble sort (worst case of Θ(n2) in computational complexity terms), or a more sophisticated approach such as a quick sort (which is Θ(n log n) on average). It is safe to say, though, that doubling the number of items in an array will more than double the number of times the comparator function is called.
The remedy for our slow comparator is to pre-compute the keys for the comparison. We can do most of the expensive work in an initial loop and store the result with jQuery's .data() method, which sets...
