Solved

# Can't quite understand a merge sort!

Posted on 2005-04-14
Medium Priority
304 Views
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
Question by:Portal111
1 Comment

LVL 11

Accepted Solution

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.

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

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
###### Suggested Courses
Course of the Month13 days, 10 hours left to enroll