Draft:Monotonic Sort
Submission declined on 2 August 2019 by I dream of horses (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.
Where to get help
How to improve your article
You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Editor resources

 Comment: Generally, we need 35 sources. I dream of horses (My talk page) (My edits) @ 08:34, 2 August 2019 (UTC)
This user has made a public declaration indicating that they have a conflict of interest with regard to the following Wikipedia article(s): 
Class  Sorting algorithm 

Data structure  Array 
Worstcase performance  
Bestcase performance  
Average performance  
Worstcase space complexity 
In computer science, montonic sort is an efficient, generalpurpose, stable noncomparative 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 introsort/quicksort.
Monotonic sort uses a nonascending or nondescending 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.
Contents
Assigning monotonic function values[edit]
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 floatingpoint value, it can be converted to an integer value, still maintaining the monotonic property.
A simple way to make this conversion is:
 If the floatingpoint value is positive, get the binary representation of the floatingpoint value and use the integer number that corresponds to that binary representation.
 If the floatingpoint value is negative, get the binary representation of the additive inverse of floatingpoint 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.
Direct approch[edit]
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.
Direct implementation[edit]
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
An example[edit]
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:
X  Y  

13  12  25 
13  7.5  5.5 
7  12  19 
7  7.5  0.5 
42  12  54 
42  7.5  34.5 
Sorting the monotonic values with the radix sort and applying its permutations to the array of pairs (x,y) gives:
X  Y  

13  7.5  5.5 
7  12  19 
13  12  25 
42  7.5  34.5 
42  12  54 
7  7.5  0.5 
Shifting the elements assigned with negative monotonic function values to the beginning of the array gives:
X  Y  

7  7.5  0.5 
13  7.5  5.5 
7  12  19 
13  12  25 
42  7.5  34.5 
42  12  54 
and the array is sorted.
Parallel sorting[edit]
The original input array can be splitted to several nonoverlapping 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.
External links[edit]
Category:Articles with example C code
Category:Sorting algorithms
Category:Stable sorts