CODEWITHSUNDEEP
javascriptarrayssorting
Dekel
Dekel

Reputation: 62556

Is it possible to cause endless-loop in a sorting function in javascript?

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.

Upvotes: 4

Views: 1909

Answers (2)

user2864740
user2864740

Reputation: 61875

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.

Upvotes: 5

beoliver
beoliver

Reputation: 5759

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.

Upvotes: 1

Related Questions