<p>According <a href="http://possiblywrong.com/presentations/generic-discriminated-sorting/#/step-5" rel="nofollow">to this slide</a> - the following sorting algorithms </p>

<ul>
<li>Merge Sort</li>
<li>Insertion Sort</li>
<li>Bubble Sort</li>
<li>Quicksort</li>
<li>Bogosort</li>
</ul>

<p>all rely on <code>cmp</code> - which has a fixed upper limit of <code>n log n</code>. </p>

<p><a href="http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011a.pdf" rel="nofollow">Ralf Hinze's Discriminator sort</a> is incredibly performant in linear time. According <a href="http://possiblywrong.com/presentations/generic-discriminated-sorting/#/step-60" rel="nofollow">to these tests</a> in Scala it runs faster than cmp-based sorts for a linear operation. </p>

<p>My question is - can the <a href="http://www.cs.ox.ac.uk/ralf.hinze/WG2.8/31/slides/aplas2013.pdf" rel="nofollow">disciminator sort</a> be parallelized?</p>

CC BY-SA 3.0
2014-02-17T00:52:00.837Z
This looks like a radix sort or trie sort. What do you know about parallelizing those?
jbapple
CC BY-SA 3.0
2014-02-17T20:06:18.467Z
Yes, if you do a parallel merge. The TCS question is, can you formulate Hinze's discriminator as a monoid or semigroup?
Chad Brewbaker
CC BY-SA 3.0
2014-02-17T22:20:16.963Z
@ChadBrewbaker that would be a fascinating discussion.
hawkeye
CC BY-SA 3.0
2014-02-18T13:51:54.923Z
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) ?
Massimo Cafaro
CC BY-SA 3.0
2014-02-18T15:09:32.570Z
Hinze cuts GADTs off at a certain depth so you can radix/count/bucket them since you are on a fixed size domain.
Chad Brewbaker
<sorting><parallel>
Is Ralf Hinze's Discriminator sort parallelizable?
hawkeye
# Is Ralf Hinze's Discriminator sort parallelizable?

(Asked by: username_0 on 2014-02-16)

According [to this slide](http://possiblywrong.com/presentations/generic-discriminated-sorting/#/step-5) - 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](http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011a.pdf) is incredibly performant in linear time. According [to these tests](http://possiblywrong.com/presentations/generic-discriminated-sorting/#/step-60) in Scala it runs faster than cmp-based sorts for a linear operation.

My question is - can the [disciminator sort](http://www.cs.ox.ac.uk/ralf.hinze/WG2.8/31/slides/aplas2013.pdf) be parallelized?

**Tags:** sorting, parallel
> **Comments:**
> **username_1**: This looks like a radix sort or trie sort. What do you know about parallelizing those?  
> **username_2**: Yes, if you do a parallel merge. The TCS question is, can you formulate Hinze's discriminator as a monoid or semigroup?  
> **username_0**: @ChadBrewbaker that would be a fascinating discussion.  
> **username_3**: 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) ?  
> **username_2**: Hinze cuts GADTs off at a certain depth so you can radix/count/bucket them since you are on a fixed size domain.  

---

## 0 answers

