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?

  • 1
    $\begingroup$ This looks like a radix sort or trie sort. What do you know about parallelizing those? $\endgroup$
    – jbapple
    Feb 17, 2014 at 0:52
  • $\begingroup$ Yes, if you do a parallel merge. The TCS question is, can you formulate Hinze's discriminator as a monoid or semigroup? $\endgroup$ Feb 17, 2014 at 20:06
  • $\begingroup$ @ChadBrewbaker that would be a fascinating discussion. $\endgroup$
    – hawkeye
    Feb 17, 2014 at 22:20
  • $\begingroup$ 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) ? $\endgroup$ Feb 18, 2014 at 13:51
  • $\begingroup$ Hinze cuts GADTs off at a certain depth so you can radix/count/bucket them since you are on a fixed size domain. $\endgroup$ Feb 18, 2014 at 15:09


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.