0
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 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$
    – Chad Brewbaker
    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$
    – Massimo Cafaro
    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$
    – Chad Brewbaker
    Feb 18, 2014 at 15:09

0

Reset to default

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.