Portal111
asked on
Can't quite understand a merge sort!
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.
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.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.