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.

Improve this question
8
  • 3
    Yes it is possible to recursively call the callback function passed to .sort() Commented Aug 8, 2017 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. Commented Aug 8, 2017 at 23:54
  • The specific value would be the function call to the same function, else no. Commented Aug 8, 2017 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). Commented Aug 8, 2017 at 23:55
  • @guest271314 you said "else no" - care to explain? Commented Aug 8, 2017 at 23:57

2 Answers 2

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.