Search jQuery

jQuery Forum

Sorting of jQuery Set apparently takes O(n^2) time in Safari

in Using jQuery • 7 years ago

It seems like Safari can sort native JS array in O(n log n) time (which is expected) but it takes about O(n^2) time to sort jQuery set.

I have asked this question on StackOverflow but no one answered there, so I'm posting it here.

Here is the code I was using.

In a nutshell, if you have code like this on your page:

 function sortArray(a) { a.sort(compare); } function sortJQuerySet(b) { b.sort(compare); } $(document).ready(function(){ var a = [], b = [], i = 0, n = 1000; for(i=0; i<n; ++i) { a.push($('<div>' + i.toString() + '</div>')); b.push($('<div>' + i.toString() + '</div>')); } b = $(b); $('#runner').click(function(){ sortArray(a); sortJQuerySet(b); }); });

and try to profile it with Safari JS profiler, you're going to get the following results:

Sorting of the native array with 1000 elements takes about 10000 comparisons which is okay, but sorting of jQuery set takes half a million comparisons which looks like a quadratic complexity.

I would like to know the reasons behind that since it can cause problems when one wants to sort a thousand-element set on a page.

Thanks.

P.S. I'm not sure where to place this post so I chose "Ask a question" category.