Solved

# Can't quite understand a merge sort!

Posted on 2005-04-14
300 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

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

### Suggested Solutions

Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …