Re: Merge sort

På Sat, 27 Jan 2007 14:16:01 -0000, skrev Frank Kotler <fbkotler@xxxxxxxxxxx>:

//\\o//\\annabee wrote:
På Sat, 27 Jan 2007 10:23:02 -0000, skrev Foolad <fooladgh@xxxxxxxxx>:

Hello,
Can anybody help me implementing merge sort algorithm with 68000
assembly language?
I don't know where to begin.
Thanks.
Whats a merge sort?

Wannabee, let me introduce you to my friend Google!
http://en.wikipedia.org/wiki/Merge_sort

The gist of it is:

-------------------------
Conceptually, merge sort works as follows:

1. Divide the unsorted list into two sublists of about half the size
2. Sort each of the two sublists recursively until we have list sizes of length 1, in which case the list itself is returned
3. Merge the two sorted sublists back into one sorted list.

The algorithm was invented by John von Neumann in 1945.
------------------

Ok. "Sound" a like a variant of "quicksort".

These "recursive" sorts don't *sound* to me like they'd be fast, but apparently they are (depending on data, apparently).

Quicksort can be fast. So I guess mergesort will be too as they both
seems to me like a form of "binary search".
A recursive implementation is not a must. You can change a recursive
approach to a non-recurive one, in not to much of a hassle in most
cases.


Why do you want one, and what is the problem you need to solve?

Well, sounds like it might be homework. He wants to implement a merge sort in 68k assembly (Do *you* know any 68k assembly? I don't!), "why" is his business...

I am supposing 68k here means an amiga or similar.
Lets just say. I have seen it. A friend of mine swore to it the same way Herbert does.

If you don't know where to begin, Foolad, start with what you're given - the data to sort. In what form will this data be, and how will you access it? How will you determine where the "middle" is? How will you divide it into two lists? I suspect this will involve memory allocation, so learn how to do that on your system, if you don't know. Your routine will be more flexible if you can provide the actual comparison routine as a "callback". Then "repeat until done", I guess, and spew it back somehow. The "somehow" may be specified in the assignment/program-specs. Good luck!



Best,
Frank


.

Relevant Pages

  • Panic, a strange behavior of lisp program
    ... when SORT is called with a parameter that includes some that ... No actually although CLtL ... this apparent mistake in conversion from CLtL to ANSI-CL. ... Web page that lists all such "obvious" mistakes. ...
    (comp.lang.lisp)
  • RE: Incident investigation methodologies
    ... However, what sort of reaction ... Speculation gets you nowhere. ... > malware we encounter. ... > of what makes public lists useful - you can get some ...
    (Incidents)
  • Re: Detailed explanation of how a QuickSort Works
    ... Firstly, if you consider the simple "Bubble Sort" algorithm, it works by running through the entire data set, one item at a time, comparing each item to the previous item and swapping them if they are not already in the correct order. ... by simply running through the entire list just once (and splitting it into two smaller lists) you have cut the sorting time in half. ...
    (microsoft.public.vb.general.discussion)
  • Re: Ordering Products
    ... algorithms. ... lists with constrained item transpositions. ... I think while the built in sort works as a convenience, ... Overall it's about 10 times slower than pythons built in sort for large ...
    (comp.lang.python)
  • Re: Ordering Products
    ... > Kay Schluehr wrote: ... >> It would be interesting to examine some sorting algorithms on factor ... >> lists with constrained item transpositions. ... > I think while the built in sort works as a convenience, ...
    (comp.lang.python)