How to sort a JS array in batches (for performance)
<p>I have a JS application that needs to do a complicated sort of a large array and then display it. Using the built in <code>array.sort(cb)</code> method can take up to 1 second with my data. This is long enough for my UI to get janky.  </p>

<p>Because the UI is only tall enough to show a subset of the sorted array on the screen with the rest below the scroll or paginated, I had an idea. What if I made an algorithm that went through the large array and quickly did a sort in such a way that the top N items were perfectly sorted, but the remaining items in the array were imperfectly sorted. Each time I ran my algorithm it would sort a little more of the array from the top down.</p>

<p>So I could break up my processing into chunks and have a smooth UI.  For the first few seconds the array would not be perfectly sorted, but the imperfections would be below the scroll so they wouldn't be noticed. </p>

<p>My naive solution would be to write my own "Selection Sort" with the ability to break after N matches and resume later, but "Selection Sort" is a pretty terrible algorithm. The faster algorithms (from my understanding) have to go to completion to guarantee that the top N items are stable.</p>

<p>Does anyone know of an existing solution for this? Am I crazy?  Any suggestions?</p>

<p><strong>UPDATE</strong></p>

<p>Taking the idea suggested by @moreON, I wrote a custom QuickSort that bails out once it has the required precision. The native sort took 1sec for this data.  The regular QuickSort took around 250ms, which is already surprisingly better. The QuickSort that bails out after the first 100 items are sorted took a brisk 10ms, which is much much better.  I can then take an additional 250ms to finish the sort but this doesn't matter so much because the user is already looking at the data.  This reduces the user's experienced delay from 1sec to 10ms, which is pretty great.</p>

<pre><code>//Init 1 million random integers into array
var arr1 = [];
var arr2 = [];
for(var i=0;i&lt;1800000;i++) {
   var num = Math.floor(Math.random() * 1000000);
   arr1.push(num);
   arr2.push(num);
}
console.log(arr1);

//native sort
console.time("native sort");
arr1.sort(function(a,b) { return a-b; });
console.timeEnd("native sort"); //1sec
console.log(arr1);

//quicksort sort    Ref: https://www.nczonline.net/blog/2012/11/27/computer-science-in-javascript-quicksort/
function swap(arr, a, b) {
   var temp = arr[a];
   arr[a] = arr[b];
   arr[b] = temp;
}
function cmp(a,b) {
   return (a&lt;b);
}
function partition(items, left, right) {
   var pivot = items[Math.floor((right + left) / 2)];
   var i = left;
   var j = right;

   while (i &lt;= j) {
      while (cmp(items[i],pivot)) i++;
      while (cmp(pivot,items[j])) j--;
      if (i &lt;= j) {
         swap(items, i, j);
         i++;
         j--;
      }
   }
   return i;
}
function quickSort(items, left, right, max) {    
   if(max &amp;&amp; left-1 &gt; max) return items; //bail out early if we have enough
   if (items.length &gt; 1) {
      var index = partition(items, left, right);
      if (left &lt; index - 1) quickSort(items, left, index - 1, max);
      if (index &lt; right) quickSort(items, index, right, max);
   }
   return items;
}

//sort first 100
console.time("partial Quicksort");
arr2 = quickSort(arr2,0,arr2.length-1,100);
console.timeEnd("partial Quicksort"); //10ms
console.log(arr2);

//sort remainder
console.time("finishing Quicksort");
arr2 = quickSort(arr2,100,arr2.length-1); //250ms
console.timeEnd("finishing Quicksort");    
console.log(arr2);
</code></pre>