?
Solved

Can't quite understand a merge sort!

Posted on 2005-04-14
3
Medium Priority
?
304 Views
Last Modified: 2010-04-17
Hi there, i am having great difficulty at understanding the following java code for a merge sort!

public class mergeSort {
    protected NameAndNumber[] nnData = null;
    protected NNArray nn = null;
    protected int N = 0;
   
    public mergeSort(NNArray nn) {
        nnData = nn.getNNData();
        N = nn.length();
        this.nn = nn;
     }
   
    public void sort()
    {
        int n = 1;
       
        while (n <= N)
        {
            int i =0;
            while (i != N)
            {
                final int j = Math.min(N,i+n);
                final int k = Math.min(N,i+2*n);
                NameAndNumber[] t = new NameAndNumber[k - i];
                mergeSegs(i,j,k,t);
                int m = 0;
                while (i + m != k)
                {
                    nnData[i+m]=t[m];
                    ++m;
                }
                i=k;
            }
            n=2*n;
        }
       
    }
   
    protected void mergeSegs(final int i,final int j, final int k, NameAndNumber[] t)
    {
        final int M = t.length;
        int p = i;
        int q = j;
        int r = 0;
       
        while (p != j && q != k)
        {
            if (nnData[p].number <= nnData[q].number)
            {
                t[r] = nnData[p];
                ++r;
                ++p;
            }else{
                t[r] = nnData[q];
                ++r;
                ++q;
            }
        }
       
        while (p != j)
        {
            t[r] = nnData[p];
            ++r;
            ++p;
        }
       
        while (q != k)
        {
            t[r] = nnData[q];
            ++r;
            ++q;
        }
    }
   
}

I was wondering if someone could help me understand a merge sort and also how this code works!

I have been to various sites but i am finding it almost impossible to understand!

Thanks, Jack.
0
Comment
Question by:Portal111
1 Comment
 
LVL 11

Accepted Solution

by:
cup earned 2000 total points
ID: 13784563
I'll explain it with numbers.  This is a polyphase mergesort.  In the past it was used with streaming tapes to sort data.  Nowadays, it is just another disk sort.  Arrays are used to simulate the disks but if you want to use arrays, there are far less wasteful techniques.  Anyway, enough of my rambling.

Say this is your sequence

3 6 9 2 5 8 1 4 7

First it splits the sequence into blocks of 1
3 | 6 | 9 | 2 | 5 | 8 | 1 | 4 | 7

Then it merges adjacent pairs into blocks of 2
3 6 | 2 9 | 5 8 | 1 4 | 7

and again in blocks of 4
2 3 6 9 | 1 4 5 8 | 7

and again in blocks of 8
1 2 3 4 5 6 8 9 | 7

until finally the list is sorted
1 2 3 4 5 6 7 8 9
0

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In this post we will learn how to make Android Gesture Tutorial and give different functionality whenever a user Touch or Scroll android screen.
Although it can be difficult to imagine, someday your child will have a career of his or her own. He or she will likely start a family, buy a home and start having their own children. So, while being a kid is still extremely important, it’s also …
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…
Simple Linear Regression

749 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question