If you reread my posts, you will see that I knew about the built-in sort
function. However, I thought it would be nice to work on specific sort rules
as opposed to one generic sort function.
That's odd...my implementation of merge sort does not differ greatly from
the pseudocode for it in letter or spirit. Codecodex does remark that a
non-recursive implementation may be more efficient, but it does not discuss
the difference between appending to the beginning or end of a list. Overall,
however, I think the efficiency of the algorithm is ultimately decided by
the internal architecture of the application, which I would not know about
because I am not a Maxima developer.
On the other hand, I am curious as to where O(n^4) comes from. That is very
slow for a sort algorithm. Once again, it probably depends on internal
architecture.
On Fri, Jun 25, 2010 at 16:43, Richard Fateman <fateman at cs.berkeley.edu>wrote:
> Leo Butler wrote:
>
>> On Fri, 25 Jun 2010, Jeffrey Hankins wrote:
>>
>> < Thanks. That was obviously the line I intended. If you're curious, I've
>> written a few interesting things. I even found a way to write quicksort and
>> merge sort in
>> < Maxima:
>>
>> You may wish to add your code to:
>>
>> http://www.codecodex.com/wiki/Merge_sort
>> http://www.codecodex.com/wiki/Quicksort
>>
>> http://rosettacode.org/wiki/Sorting_algorithms/Merge_sort
>> http://rosettacode.org/wiki/Sorting_algorithms/Quicksort
>>
>> Leo
>>
>>
> Because of the way it is written, using endcons and append, it is not like
> quicksort, which is O(n log n).
> It is probably worse than O(n^4), whereas a normal naive sorting program is
> O(n^2).
>
>
> endcons takes time proportional to the length of the list, and is almost
> always a bad idea.
> Compare to cons, which takes constant time, and is very fast.
>
>
> I think that much better (clearer and shorter) programs could be written.
>
> There is also a "sort" program built in.
>
> Here is an outline of mergesort.
>
> mergesort(L)
> if (length(L)<=1) then L else merge
> (mergesort(leftpart(L)),mergesort(rightpart(L));
>
> you get the idea.
>
> endcons takes time proportional to the length of the list, and is almost
> always a bad idea.
> cons takes constant time, and is very fast.
>
>
>
>