[PD] sigmund list sort

[Mathieu Bouchard]

Le 2012-02-24 à 09:02:00, Frank Barknecht a écrit :
> On Sat, Feb 18, 2012 at 01:14:22PM -0500, Mathieu Bouchard wrote:
>> the [list-sort] abstraction uses a high-constant O(n²) algorithm that
>> breaks once you try to sort more than 125 values.
> Actually [list-sort] since quite some time uses the "sort" method borrowed from
> Pd's data-structures for sorting.

I have Pd-extended 42.5 that contains Michał Seta's sort, which used to be 
cubic (O(n³)) and with even lower sorting limits, until I made you replace 
the O(n²) [list-drip] that used O(n) stack, by one that runs in O(n) and 
uses O(log n) stack.

I don't know any more recent version of list-abs.

> The problem here is not so much the sorting algorithm, which is very 
> fast and can sort way more than 125 items.

Indeed, it's a slow version of mergesort written using linkedlists in C, 
which is still faster than nearly anything one could possibly come up with 
in pure Pd.

> However copying the list to a data structure and back - this currently 
> indeed has a problem with stack-overflows, as I'm now aware. Have to 
> think about a fix ...

Make sure that your algos take less than O(n) stack space... If it's not a 
125 element limit, it's 500 or 1000, and it can't get higher without 
recompiling Pd to be more indulgent.

  ______________________________________________________________________
| Mathieu BOUCHARD ----- téléphone : +1.514.383.3801 ----- Montréal, QC