|Submission declined on 2 August 2019 by talk). (|
This submission is not adequately supported by reliable sources. Reliable sources are required so that information can be verified. If you need help with referencing, please see Referencing for beginners and Citing sources.
Declined by 41 days ago. Last edited by I dream of horses 41 days ago. Reviewer: Inform author.
|Worst-case space complexity|
In computer science, montonic sort is an efficient, general-purpose, stable non-comparative sorting algorithm which is based on the radix sort and sorts data by reducing the sorting problem to an integer sorting problem which can be solved in linear time complexity. Developed by Ido Dov Cohen in 2019. When implemented well, it can be about two or three faster than intro-sort/quick-sort.
Monotonic sort uses a non-ascending or non-descending monotonic function to determine the order of the elements. It sorts the monotonic function values assigned to the elements in the array via an LSD or MSD radix sort and applies the same permutations to the elements array, effectively sorting it as well.
When the monotonic values contain negative values, the LSD radix sort places them in the end of the array due to the two’s complement method, which sets the most significant bit of the monotonic function value to 1. After performing the LSD radix sort, the elements assigned with negative monotonic function values, should be shifted from the end of the array to its beginning, maintaining their internal order.
Assigning monotonic function values
Arrays of elements sorted with comparative sorting algorithm can be sorted with the monotonic sort by using the comparison key as the monotonic function value. When the comparison key is integer, using it as the monotonic function value is trivial.
In cases where the comparison key is a floating-point value, it can be converted to an integer value, still maintaining the monotonic property.
A simple way to make this conversion is:
- If the floating-point value is positive, get the binary representation of the floating-point value and use the integer number that corresponds to that binary representation.
- If the floating-point value is negative, get the binary representation of the additive inverse of floating-point value and use the additive inverse of the integer that corresponds to that binary representation.
However, these are not the only ways to determine which monotonic function values should be assigned to elements and it depends on the problem.
Conceptually, a monotonic sort works as follows:
- Assign a monotonic function value to each element in the array.
- Sort the monotonic function values array with an radix sort.
- Apply the permutations made on the array of the monotonic function values to the elements array as well.
- Move elements assigned with negative monotonic function values to the beginning of the array.
Example pseudo code:
function ModifiedLsdRadixSort(elements,monotonicVals) indices = array of n integers; for i=0 to w [elements, monotonicVals] = SortByChunkIndex(i, elements, monotonicVals); end for return indices; end function function SortByChunkIndex(index, elements, monotonicVals) elementBuckets = array of R arrays of objects; valBuckets = array of R arrays of integers; for i = 0 to n c = chunk #index of element[i]; elementBuckets[c].Add(element[i]); valBuckets[c].Add(monotonicVals[i]); end for for i = 0 to R elements.AddRange(elementBuckets[i]); monotonicVals.AddRange(valBuckets[i]); end for Return [elements, monotonicVals]; end function function MonotonicSort(elements) monotonicValues = array of n integers; negativeCount = 0; for i = 0 to n monotonicValues[i] = elements[i].GetMonotonicHint(); if (monotonicValues[i] < 0) negativeCount++; end if end for ModifiedLsdRadixSort(elements, monotonicValues); copy last negativeCount elements to temporary buffer. shift all elements <negativeCount> elements toward the end of the array. copy the elements in the temporary buffer to the start of the array. end function
We’ll use the monotonic sort to solve the X + Y sorting problem in quadratic time.
Given an original unsorted list X: 13, 7, 42 and Original unsorted list Y: 12, -7.5.
The Cartesian product of the X and Y lists: (13, 12), (13,-7.5), (7, 12), (7, -7.5), (42, 12), (42, -7.5)
All we need to do is use the monotonic function:
Sorting the monotonic values with the radix sort and applying its permutations to the array of pairs (x,y) gives:
Shifting the elements assigned with negative monotonic function values to the beginning of the array gives:
and the array is sorted.
The original input array can be splitted to several non-overlapping partitions, where each partition contains elements assigned with monotonic function values from a certain range. Those partitions can be monotonically sorted in parallel and then reassembled as one array.