0

I am trying to sort large Array list of Arrays using below code 

function _stInd(arr, ind){
  return arr.sort(function(a, b) {
    var _1 = a[ind];
    var _2 = b[ind];
    return (_1 < _2) ? -1 : (_1 > _2) ? 1 : 0;
  });
}

Please look at this bin for more info http://jsbin.com/UqEPOfa/3/edit

The code is working fine and it is able to sort also. But the problem is it is taking too much if I am trying to sort more than 1 million list of arrays based on one index.

Please suggest me to improve this code

Exception
  • 8,111
  • 22
  • 85
  • 136
  • 1
    Suggested style improvement: `return a[ind] - b[ind]`. It just needs to be positive/negative/zero, not `-1`, `1`, `0`. – Nicole Sep 04 '13 at 08:02
  • 3
    A million arrays will take a long time no matter what you do. Sorting is `O(n log n)` at best... – Niet the Dark Absol Sep 04 '13 at 08:02
  • 2
    Sorting large lists is always a problem. However contrary to what Kolink says, you can go faster than O (n log n) if you are sorting within a finite set. If you are sorting integers within a limited range, have a look at counting sort (http://en.wikipedia.org/wiki/Counting_sort), radix sort (http://en.wikipedia.org/wiki/Radix_sort) or bucket sort (http://en.wikipedia.org/wiki/Bucket_sort). – MrP Sep 04 '13 at 08:04
  • @MrP In my example I have used integers as an example but there is a scope that I may need to sort strings. – Exception Sep 04 '13 at 08:08
  • The same can apply for strings, given they are in a limited range. If this is not the case, an alternative solition will have to be found. – MrP Sep 04 '13 at 08:27

1 Answers1

1

I would suggest you to do two specific things:

  1. Take in consideration the data-set you would need to sort, that usually helps in sorting faster. (as mentioned in the comment, if its limited range do a counting sort)

  2. Start using multi-threading (actually called worker threads). YES JAVASCRIPT DOEST SUPPORT IT NOW. So do a merge sort and start showing results partially. For more details on how to use multi-threading, refer worker threads. One good tutorial I can think of is http://ejohn.org/blog/web-workers/

Neeraj
  • 8,408
  • 8
  • 41
  • 69
  • Could you please let me know how do you sort a single array using multiple threads?. If I want to use threading in this case web workers help only for non blocking UI, not to improve the performance. Regarding your first point it helps me to sort only numbers not strings. – Exception Sep 04 '13 at 08:09
  • http://en.wikipedia.org/wiki/Merge_sort. Guess you need more experience with algorithms. – Neeraj Sep 04 '13 at 08:11
  • 1. Webworkers help you do a task in the background. So imagine a scenario where you have 4 webworkers working on sorting the array. that makes the operation (theoretically) four times faster than it would have really taken. 2. If you are sorting strings, use localCompare. http://stackoverflow.com/questions/51165/how-do-you-do-string-comparison-in-javascript – Neeraj Sep 04 '13 at 08:20