Is there any built-in JavaScript function to do a partial sort? If not, what is a good way to implement it?

Given an unsorted array of *N* elements, I would like to find *K* elements that are minimal with respect to some weighting function. *K* is much smaller than *N*, so it would be inefficient to sort the whole array and take the first *K* elements.

I would be happy even if there was something non-standard, browser-dependent. I could still fallback to the custom JavaScript implementation.

PS: This is my current custom implementation (without taking a weighting function into account, just sorting the elements as they are for simplicity):

function bisect(items, x, lo, hi) { var mid; if (typeof(lo) == 'undefined') lo = 0; if (typeof(hi) == 'undefined') hi = items.length; while (lo < hi) { mid = Math.floor((lo + hi) / 2); if (x < items[mid]) hi = mid; else lo = mid + 1; } return lo; } function insort(items, x) { items.splice(bisect(items, x), 0, x); } function partialSort(items, k) { var smallest = []; for (var i = 0, len = items.length; i < len; ++i) { var item = items[i]; if (smallest.length < k || item < smallest[smallest.length - 1]) { insort(smallest, item); if (smallest.length > k) smallest.splice(k, 1); } } return smallest; } console.log(partialSort([5, 4, 3, 2, 1, 6, 7, 8, 1, 9], 3));

The algorithm walks through the given array one single time, keeping track of a sorted list of the *k* smallest items so far, using binary search to insert new elements.

Please post alternative solutions if you think they might be faster or more elegant. Timings are very welcome.

## Answer

No. There’s only the full array `sort`

, so you will need to use your own implementation.

Little improvement on your code (I had thought of exactly the same algorithm :-)):

function partialSort(items, k) { var smallest = items.slice(0, k).sort(), max = smallest[k-1]; for (var i = k, len = items.length; i < len; ++i) { var item = items[i]; if (item < max) { insort(smallest, item); smallest.length = k; max = smallest[k-1]; } } return smallest; }

(Even seems to be a little faster, I guess due to caching the `max`

variable)