Skip to main content

Array.sort

sortorder onbyon_problems

Group: Calculations
Aliases: order_by

Documentation​

Sort the array.

By default, elements are sorted in ascending order. This is a stable sort, meaning that items that compare the same will not have their order changed by the sorting process.

Arguments​

  • order: The order in which the array elements are sorted.
  • on: A projection from the element type to the value of that element being sorted on. If set to Nothing (the default), identity function will be used.
  • by: A function that compares the result of applying on to two elements, returning an an Ordering if the two elements are comparable or Nothing if they are not. If set to Nothing (the default argument), Ordering.compare _ _ method will be used.
  • on_problems: A Problem_Behavior specifying what should happen if two incomparable values are encountered.

Examples​

Sorting an array of numbers.​

      [5, 2, 3, 45, 15].to_array.sort == [2, 3, 5, 15, 45].to_array

Sorting an array of Pairs on the first element, descending.​

      [Pair 1 2, Pair -1 8].to_array.sort Sort_Direction.Descending (_.first)

Sorting an array with elements with different comparators. Values 1​

and My_Type have different comparators. 1 will be sorted before My_Type because it has the default comparator.

      [My_Type.Value 'hello', 1].to_array.sort == [1, My_Type.Value 'hello'].to_array

Remarks​

Computational Complexity​

The complexities for this sort are:

  • Worst-Case Time: O(n * log n)
  • Best-Case Time: O(n)
  • Average Time: O(n * log n)
  • Worst-Case Space: O(n) additional

Incomparable values​

Incomparable values are either values with different comparators or with the same comparator returning Nothing from its compare method. See the documentation of the Ordering module for more info.

Implementation Note​

The sort implementation is based upon an adaptive, iterative mergesort that requires far fewer than n * log(n) comparisons when the array is partially sorted. When the array is randomly ordered, the performance is equivalent to a standard mergesort.

Multiple comparators​

Elements with different comparators are incomparable by definition. This case is handled by first grouping the self array into groups with the same comparator, recursively sorting these groups, and then merging them back together. The order of the sorted groups in the resulting array is based on the order of fully qualified names of the comparators in the self array, with the exception of the group for the default comparator, which is always the first group.

Additionally, an Incomparable_Values dataflow error will be returned if the on_problems parameter is set to Report_Error, or a warning attached if the on_problems parameter is set to Report_Warning in case of encountering incomparable values.

It takes equal advantage of ascending and descending runs in the array, making it much simpler to merge two or more sorted arrays: simply concatenate them and sort.