natural merge sort with linked list in java

Question

I am looking for sample code in java for a natural merge sort using linked lists. Doing the natural merge sort iteratively not recursively. Can someone help with this or point me to a resource where I can find this?

Answer 1

class NaturalMergeSort

{

protected int originalArray[];

protected int sortedArray[];

protected int subArray[];

protected int tempArray[];

public NaturalMergeSort(int A[])

{

int N = A.length;

originalArray = new int[N];

for (int iLoop=0; iLoop<N; iLoop++)

{

originalArray[iLoop]=A[iLoop];

}

}

public void Go()

{

int iStartPos = 1;

int iStopPos = 0;

int N = originalArray.length;

int iIndexPos=1;

sortedArray = new int[1];

sortedArray[0]=originalArray[0];

int subArraySize=0;

while (iIndexPos<N)

{

iStopPos = iIndexPos;

System.out.println(" start pos = " + iStartPos + " : stop pos = " + iStopPos + " : iIndexPos = " + iIndexPos);

while (originalArray[iStopPos]>=originalArray[iStopPos-1])

{

iStopPos++;

if (iStopPos>=N)

{

iStopPos=N-1;

break;

}

}

System.out.println(" sorted run from index " + iStartPos + " to " + iStopPos);

subArraySize = iStopPos - iStartPos;

subArray = new int[subArraySize];

int subArrayIndex=0;

for (int iLoop=iStartPos; iLoop<iStopPos; iLoop++)

{

subArray[subArrayIndex++]=originalArray[iLoop];

}

tempArray = new int[subArraySize+sortedArray.length];

Merge(sortedArray,subArray,tempArray);

sortedArray = tempArray;

subArray=tempArray=null;

iStartPos = iStopPos;

iIndexPos = iStartPos+1;

}

subArray = new int[1];

subArray[0]= originalArray[N-1];

tempArray = new int[sortedArray.length+1];

Merge(sortedArray,subArray,tempArray);

sortedArray = tempArray ;

}

public int [] GetSortedArray()

{

int N = sortedArray.length;

int A[] = new int[N];

for (int iLoop=0; iLoop<N; iLoop++)

{

A[iLoop]= sortedArray[iLoop];

}

return(A);

}

public void Merge( int L[], int R[], int arr[] )

{

int i = 0; //Initial index and size of first subarray

int n1 = L.length;

int j = 0; // Initial index and size of second subarray

int n2 = R.length;

int k = 0; // Initial index and size of merged array

int N = n1+n2;

//Merge happens here

while (i < n1 && j < n2)

{

if (L[i] <= R[j])

{

arr[k] = L[i];

i++;

}

else

{

arr[k] = R[j];

j++;

}

k++;

}

//One of the arrays shall be empty...

// Copies the remaining elements of L[], if there are any

while (i < n1)

{

arr[k] = L[i];

i++;

k++;

}

// Copies the remaining elements of R[], if there are any

while (j < n2)

{

arr[k] = R[j];

j++;

k++;

}

} //Merge

public static void main(String args[])

{

int A[] = { 26, 12,13,14,15,16,17,18,19,20,21, 26, 18, 39, 40, 41, 42, 24, 33, 34, 35, 36, 42, 25, 26, 27, 28, 29, 43, 27, 31, 28, 36, 21, 22, 23, 24, 37};

int N = A.length;

NaturalMergeSort x = new NaturalMergeSort(A);

x.Go();

int a[] = x.GetSortedArray();

for (int iLoop=0; iLoop<a.length; iLoop++) { System.out.print(a[iLoop] + " "); }

}

}