Which algorithm does Array.sort() resemble?

[codegoboom]

In order to understand how sorting unfolds, I suspect that a name for the process would be a nifty starting point... any guesses? :)

[liorean]

As I understand it, it's a quicksort derivate. Knowing nothing about that algorithm, however, I might be dead wrong about this, so let's see what the specification say instead:15.4.4.11 Array.prototype.sort (comparefn)

The elements of this array are sorted. The sort is not necessarily stable (that is, elements that compare equal do not necessarily remain in their original order). If comparefn is not undefined, it should be a function that accepts two arguments x and y and returns a negative value if x < y, zero if x = y, or a positive value if x > y.

If comparefn is not undefined and is not a consistent comparison function for the elements of this array (see below), the behaviour of sort is implementation-defined. Let len be ToUint32(this.length). If there exist integers i and j and an object P such that all of the conditions below are satisfied then the behaviour of sort is implementation-defined:

• 0 ≤ i < len
• 0 ≤ j < len
• this does not have a property with name ToString(i)
• P is obtained by following one or more [[Prototype]] properties starting at this
• P has a property with name ToString(j)

Otherwise the following steps are taken.

1. Call the [[Get]] method of this object with argument "length".
2. Call ToUint32(Result(1)).
3. Perform an implementation-dependent sequence of calls to the [[Get]] , [[Put]], and [[Delete]] methods of this object and to SortCompare (described below), where the first argument for each call to [[Get]], [[Put]], or [[Delete]] is a nonnegative integer less than Result(2) and where the arguments for calls to SortCompare are results of previous calls to the [[Get]] method.
4. Return this object.

The returned object must have the following two properties.

• There must be some mathematical permutation π of the nonnegative integers less than Result(2), such that for every nonnegative integer j less than Result(2), if property old[j] existed, then new[π(j)] is exactly the same value as old[j],. but if property old[j] did not exist, then new[π(j)] does not exist.
• Then for all nonnegative integers j and k, each less than Result(2), if SortCompare(j,k) < 0 (see SortCompare below), then π(j) < π(k).


Here the notation old[j] is used to refer to the hypothetical result of calling the [[Get]] method of this object with argument j before this function is executed, and the notation new[j] to refer to the hypothetical result of calling the [[Get]] method of this object with argument j after this function has been executed.

A function comparefn is a consistent comparison function for a set of values S if all of the requirements below are met for all values a, b, and c (possibly the same value) in the set S: The notation a <CF b means comparefn(a,b) < 0; a =CF b means comparefn(a,b) = 0 (of either sign); and a >CF b means comparefn(a,b) > 0.

• Calling comparefn(a,b) always returns the same value v when given a specific pair of values a and b as its two arguments. Furthermore, v has type Number, and v is not NaN. Note that this implies that exactly one of a <CF b, a =CF b, and a >CF b will be true for a given pair of a and b.
• a =CF a (reflexivity)
• If a =CF b, then b =CF a (symmetry)
• If a =CF b and b =CF c, then a =CF c (transitivity of =CF)
• If a <CF b and b <CF c, then a <CF c (transitivity of <CF)
• If a >CF b and b >CF c, then a >CF c (transitivity of >CF)

NOTE The above conditions are necessary and sufficient to ensure that comparefn divides the set S into equivalence classes and that these equivalence classes are totally ordered.

When the SortCompare operator is called with two arguments j and k, the following steps are taken:

1. Call ToString(j).
2. Call ToString(k).
3. If this object does not have a property named by Result(1), and this object does not have a property named by Result(2), return +0.
4. If this object does not have a property named by Result(1), return 1.
5. If this object does not have a property named by Result(2), return –1.
6. Call the [[Get]] method of this object with argument Result(1).
7. Call the [[Get]] method of this object with argument Result(2).
8. Let x be Result(6).
9. Let y be Result(7).
10. If x and y are both undefined, return +0.
11. If x is undefined, return 1.
12. If y is undefined, return −1.
13. If the argument comparefn is undefined, go to step 16.
14. Call comparefn with arguments x and y.
15. Return Result(14).
16. Call ToString(x).
17. Call ToString(y).
18. If Result(16) < Result(17), return −1.
19. If Result(16) > Result(17), return 1.
20. Return +0.

NOTE Because non-existent property values always compare greater than undefined property values, and undefined always compares greater than any other value, undefined property values always sort to the end of the result, followed by non-existent property values.

NOTE The sort function is intentionally generic; it does not require that its this value be an Array object. Therefore, it can be transferred to other kinds of objects for use as a method. Whether the sort function can be applied successfully to a host object is implementation-dependent.Note that this formalisation of the algorithm does not match that of Netscape, which uses a stable sort.

[codegoboom]

Wow, that's a eyeful! :eek:
Quicksort literature it just might be... thanks.

[jkd]

Doesn't sound like QuickSort at all. If it mentions a pivot, then it's quicksort. That blurb doesn't seem to. As a matter of fact, it just describes in detail how the comparison function is supposed to work... I don't see a mention of any particular algorithm. Just how to iterate through the Array members to pass them to comparefn.

[codegoboom]

I had thought of somehow deducing an answer from several comparefn outputs--but of course, I'd need at least a general knowledge of the whole algo-lot, up front; so um... that's plan-B, I guess. :D

[liorean]

Had a little look at Mozilla's implementation. <http://lxr.mozilla.org/seamonkey/source/js/src/jsarray.c>

Names indicate they are using heapsort, even though low, high and pivot variables exists and qsort is mentioned in a comment.

[codegoboom]

Hmm, a mixture of sorts... :)

It looks like JScript uses QuickSort, but it's unclear to me whether that's always been the case, as the following appears only in .Net documentation:


Array.Sort Method (Array) (http://msdn.microsoft.com/library/en-us/cpref/html/frlrfsystemarrayclasssorttopic1.asp)

Sorts the elements in an entire one-dimensional Array using the IComparable interface implemented by each element of the Array.

Remarks

Each element of array must implement the IComparable interface to be capable of comparisons with every other element in array.

If the sort is not successfully completed, the results are undefined.

This method uses the QuickSort algorithm. This is an O(n ^2) operation, where n is the number of elements to sort, with an average of θ(n log n).

This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.



System.Array.Sort vs. Array.sort methods... they don't appear to be contrasted much--other than System.Array (which is said to be "overloaded") being required between languages.

Doesn't Array.sort handle multi-dimensions, though?


That would be no... :D
Although JScript does not directly support multi-dimensional arrays, you can store any sort of data inside array elements — including other arrays. So you can get the behavior of multi-dimensional arrays by storing arrays within the elements of another array.

[david_kw]

Lol. I was just reading a book that claimed the internal form of the Array.sort() function was a bubble sort algorithm. I found that very, very, VERY hard to believe so I did a google search and end up right back here again with liorean and jkd answering my question. Go figure. =P

Anyway, I doubted it was true (who uses a bubble sort in RL?), but still glad to get confirmation. Even if it was 2 years before I asked the question.

david_kw