4

Array.prototype.sort sorts the elements of the array in-place and return the sorted array.

The requirements from the compareFunction(a, b) are:

  1. get two elements (to compare)
  2. return <0 in order to place a before b
  3. return 0 in order to keep the original position of a and b (relative to each other)
  4. return >0 in order to place b before a.
  5. the returned value must always be the same for each pair of elements.

Since every browser-provider might implement the sorting algorithm differently, my question is: is possible to provide a compareFunction that will cause the sort function to get into an infinite loop while trying to sort the elements?

If so - in case it is possible - would it be considered a bug in the implementation, or in case the compareFunction did not follow the above instructions - it's okay to get unexpected results?

To be clear - I'm not asking if it's possible to add while (true); inside the compareFunction.

user2864740
  • 60,010
  • 15
  • 145
  • 220
Dekel
  • 60,707
  • 10
  • 101
  • 129
  • 3
    Yes it is possible to recursively call the callback function passed to `.sort()` – guest271314 Aug 08 '17 at 23:53
  • Same as `while(true);`. I'm asking if it's possible to return specific values that will cause the `sort` function to get into endless-loop while trying to sort. – Dekel Aug 08 '17 at 23:54
  • The specific value would be the function call to the same function, else no. – guest271314 Aug 08 '17 at 23:55
  • Not what I'm asking... consider a sorting function that return a specific value (not a recursive call to the same function). – Dekel Aug 08 '17 at 23:55
  • @guest271314 you said "else no" - care to explain? – Dekel Aug 08 '17 at 23:57
  • At text of Question _"that will cause the sort function to get into an infinite loop"_ , _"get two elements (to compare) return <0 in order to place a before b return 0 in order to keep the original position of a and b (relative to each other) return >0 in order to place b before a. the returned value must always be the same for each pair of elements."_. Where the expected return value from the function passed to `.sort()` is either a `Number` or a `Boolean`, what you are asking about the probability of is not possible without actively trying to do so. – guest271314 Aug 08 '17 at 23:58
  • @Dekel If "the returned value must always be the same for each pair of elements" is held then, no. It's not possible under any sort implementation that conforms to the specification rules. Although even if was *not* held I doubt there is any mainstream sort algorithm that would not terminate (eg. mergesort, quicksort, bubble *always* reduce) - produce the "wrong" answer, sure. – user2864740 Aug 09 '17 at 00:08
  • The predominant sorting algorithms terminate by different criteria and will not repeatedly attempt to sort if you give it a comparison function by which sorting is impossible. – ASDFGerte Aug 09 '17 at 00:08

2 Answers2

5

No.

Proper sort algorithms (quicksort, merge-sort, Tim-sort, bubble-sort, etc.) always make progress on each iteration and are thus free from the possibility of endless loops like this. While it is possible to craft a function to attack the performance of specific sort implementations, this will not prevent termination of the algorithm.

Hypothetically, it is possible that a "custom" sort implementation could be written in a way where an unstable comparison function (which makes the calling function invalid and the result unpredictable) could "hang", this is simply a serious defect in the sorting implementation; I give much more credit to the authors/contributors of widely used and thoroughly vetted sort implementations used in browsers.

user2864740
  • 60,010
  • 15
  • 145
  • 220
1

The sorting algorithms used assume that the items to be sorted form a total order. This means that given say 'a','b','c' there is exactly one order. perhaps 'b' 'a' 'c'. Assuming that your compare function was only comparing two items (not calling a function that would not terminate) then if your comparison function is not well defined then the total order would not be well defined.

i.e if b < c and c < b then which one comes first? b or c.

so if you had a compare function like this (not real code):

compare(a,b) = select at random from [-1, 0, 1]

then when called with the same values the result might be different. It would also mean that there was not a well defined ordering - while this would not guarantee an infinite loop, but might go on a while - then again it might also stop quickly! But in general I would say no, as this would not be a well defined comparison.

beoliver
  • 5,579
  • 5
  • 36
  • 72