Re: Merge sort

//\\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! Here's the Official US Gubmint definition:

http://www.nist.gov/dads/HTML/mergesort.html

The Wikipedia entry is more useful:

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.
------------------

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

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...

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)