I'm currently working on a personal project involving functional reactive JavaScript, and I've come up with an odd question. Note that this question is not JavaScript specific, but that is the context in which I am asking it.


When filtering a collection of data, you end up with a smaller set of data. Therefore, correctly filtering your data earlier (rather than later) ends up optimizing your later code, as it does not need to iterate through the portion of data which will not be used. (think filtering before mapping, instead of visa-versa)

However, I was wondering if there's a scenario in which sorting provides similar benefits, or if sorting is generally used as a way of formatting data to be displayed, so that an end user may more easily absorb it (sort by name, city, state, etc).


When is sorting your data more desirable than sorting the corresponding views of that data?

  • 1
    When the client does not display the whole dataset at once. Sorting is filtering then. – Patrick Jan 15 '13 at 15:12
  • Excellent observation. This is also something I'll need to look into. – cwharris Jan 15 '13 at 15:12
  • 1
    Sorting may be a preprocessing to filtering: think of sort -u – mouviciel Jan 15 '13 at 15:22

Well the obvious answer is that for some data structures knowing that the data is already sorted changes lookups from O(n) to O(log n) e.g. finding an element in an array using binary search rather than linear.

I'm not sure how useful this is to you if you are doing FRP though, one assumes that FRP means you probably aren't using array like structures in the first place?

I'd also point out that this is a bit different than filter then map. the map gains the benefit of a previous filter without needing any knowledge of the filter. binary search however requires knowing the data is sorted.

  • Definitely. I appreciate the response. I'm looking for more of a client-side scenario with clear performance benefits, rather than a server-side scenario where every micro-second might count. Most of my lookups will be using a filter function, rather than a dictionary (that's just the nature of the beast I'm working with, for now). – cwharris Jan 15 '13 at 15:04
  • "One assumes that FRP means you probably aren't using array like structures in the first place." - That's basically what I'm addressing with this question. I'm attempting to create an observable collection which yields all of it's items to all subscribers, but all of it's items are "lifetime" observables which should be "removed" from the subscriber when they complete/dispose. I'm wondering if I should yield those items in order, and provide some sorting functionality, or simply pass the sorting function to the subscriber along with the items in the collection. – cwharris Jan 15 '13 at 15:09
  • This answer has been revealing and thought provoking. I'll most likely mark this as the answer, unless another answer blindsides me with some kind of revelation. ;) – cwharris Jan 15 '13 at 15:14
  • assuming the all your subscribers need the same sort I think you could view it as a possible optimization technique there too. of course if different subscribers need different sort orders then this is no longer possible. – jk. Jan 15 '13 at 15:16
  • The only problem I'm thinking about when assuming all subscribers will have the same sort function, is figuring what to do when the sort function changes. Should all "lifetime" observables be removed and reissued in a sorted manner, should each lifetime have some kind of sorting observable associated with it (number indicating it's place in the sort, for instance), or some other kind of handling. The idea is to make this as "push"-based as possible, and as efficient as possible (within reason, obviously), because this will all be put into a reusable library. – cwharris Jan 15 '13 at 16:19

Various scenarios spring to mind, the textbook ones being searches and finding minimum / maximum values; on a sorted list, searching is typically O(log n) and min/max is O(1), while on an unsorted list, you'll get O(n) for both.

Besides that, depending on what you need to do with your data, other optimizations may be possible that exploit sortedness of a list - think of things like axis sorting in collision detection.

  • 1
    +1 yes min/max is another obvious one, of course if you only need min/max then just caching this is probably better which suggests that any data transformation is sort of a caching strategy for the views which use it. – jk. Jan 15 '13 at 15:44
  • Of course, if min/max is all you need, a linear traversal of the unsorted list (O(n)) is cheaper than sorting (O(n log n)) plus fetching first and last element (O(1) or O(n), depending on the list data structure used). – tdammers Jan 15 '13 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.