m_sort Module

• Uses:

• variableKind

Module containing in-place and indirect routines to sort an array of numbers.

Uses an introspective sort on a set of number. See this http://www.geeksforgeeks.org/know-your-sorting-algorithm-set-2-introsort-cs-sorting-weapon/ for more information

To begin, a quicksort with a median of three pivot is used until the size of the array is less than 16. At this point, an insertion sort is used to reduce cache overhead and tail recursion. Unfortunately, a quicksort is not ideal for sorted/almost sorted arrays or arrays with duplicate values. Therefore if the number of iterations exceededs a threshold, a heapsort is used instead. This provides a robust sorting algorithm that is still very fast for almost sorted arrays.

In this implementation, the quicksort and heapsort are unstable sorts. A stable merge sort is therefore provided as an alternative but it has an order(N) memory overhead.

Often, the numbers wish to be maintained in their given order, so with an O(N) memory overhead we can sort an integer array instead by calling argsort()

See sort and argSort for more information.

Used By