5.3.19.4. Stable and Unstable Sorts

Note

The current implementation is using the same stable sort algorithm for both the sort and the stableSort method of the Array class.

As such, below discussion of the difference between a stable and an unstable sort does not apply currently.

The default sorting algorithm is an unstable sort. In an unstable sort, items are not guaranteed to maintain their original positions if they compare equal during the sort. Consider the following simple example:

Example 5.215. Unstable sort

a = .array~of("Fred", "George", "FRED", "Mike", "fred")
a~sortwith(.caselesscomparator~new)
do name over a
  say name
end

This example displays the 3 occurrences of Fred in the order "Fred", "fred", "FRED", even though they compare equal using a caseless comparison.

The Array class implements a second sort algorithm that is available using the stableSort and stableSortWith methods. These methods use a Mergesort algorithm, which is less efficient than the default Quicksort and requires additional memory. The Mergesort is a stable algorithm that maintains the original relative ordering of equivalent items. Our example above, sorted with stableSortWith, would display "Fred", "FRED", "fred".