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.