# Is Ralf Hinze's Discriminator sort parallelizable?

According to this slide - the following sorting algorithms

• Merge Sort
• Insertion Sort
• Bubble Sort
• Quicksort
• Bogosort

all rely on cmp - which has a fixed upper limit of n log n.

Ralf Hinze's Discriminator sort is incredibly performant in linear time. According to these tests in Scala it runs faster than cmp-based sorts for a linear operation.

My question is - can the disciminator sort be parallelized?

• This looks like a radix sort or trie sort. What do you know about parallelizing those? Feb 17, 2014 at 0:52
• Yes, if you do a parallel merge. The TCS question is, can you formulate Hinze's discriminator as a monoid or semigroup? Feb 17, 2014 at 20:06
• @ChadBrewbaker that would be a fascinating discussion. Feb 17, 2014 at 22:20
• Is this a general purpose sorting algorithm or does it require additional assumptions on the input (this is the case for radix sort, counting sort and bucket sort) ? Feb 18, 2014 at 13:51
• Hinze cuts GADTs off at a certain depth so you can radix/count/bucket them since you are on a fixed size domain. Feb 18, 2014 at 15:09