[PD] sigmund list sort

[Jonathan Wilkes]

----- Original Message -----
> From: Mathieu Bouchard <matju at artengine.ca>
> To: Frank Barknecht <fbar at footils.org>
> Cc: pd-list at iem.at
> Sent: Friday, February 24, 2012 1:26 PM
> Subject: Re: [PD] sigmund list sort
> 
> 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 ...

Use an iterative loop instead of a recursive one and you will avoid the stack overflows.

> 
> 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
> _______________________________________________
> Pd-list at iem.at mailing list
> UNSUBSCRIBE and account-management -> 
> http://lists.puredata.info/listinfo/pd-list
>