hola,

I really need your help on this. I tried to do k-way merge sort in c# and finally I ended with this:

public ArrayList MergeSort ( ArrayList arrIntegers ) {
if (arrIntegers.Count == 1) {
return arrIntegers;
}
ArrayList arrSortedInt = new ArrayList();
int middle = (int)arrIntegers.Count/2;
ArrayList leftArray = arrIntegers.GetRange(0, middle);
ArrayList rightArray = arrIntegers.GetRange(middle, arrIntegers.Count - middle);
leftArray =  MergeSort(leftArray);
rightArray = MergeSort(rightArray);
int leftptr = 0;
int rightptr=0;
for (int i = 0; i < leftArray.Count + rightArray.Count; i++) {
if (leftptr==leftArray.Count){
rightptr++;
}else if (rightptr==rightArray.Count){
leftptr++;
}else if ((int)leftArray[leftptr]<(int)rightArray[rightptr]){
//need the cast above since arraylist returns Type object
leftptr++;
}else{
rightptr++;
}
}
return arrSortedInt;
}

But this is only two way sorting, I would like to change it and make it n-way merge sorting.

Try this code:

// array of integers to hold values
private int[] a = new int[100];
private int[] b = new int[100];

// number of elements in array
private int x;

// Merge Sort Algorithm
public void sortArray()
{
m_sort( 0, x-1 );
}

public void m_sort( int left, int right )
{
int mid;

if( right > left )
{
mid = ( right + left ) / 2;
m_sort( left, mid );
m_sort( mid+1, right );

merge( left, mid+1, right );
}
}

public void merge( int left, int mid, int right )
{
int i, left_end, num_elements, tmp_pos;

left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;

while( (left <= left_end) && (mid <= right) )
{
if( a <= a[mid] )
{
b[tmp_pos] = a;
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
b[tmp_pos] = a[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}

while( left <= left_end )
{
b[tmp_pos] = a;
left = left + 1;
tmp_pos = tmp_pos + 1;
}

while( mid <= right )
{
b[tmp_pos] = a[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}

for( i = 0; i < num_elements; i++ )
{
a = b;
right = right - 1;
}
}

Try this code:

// array of integers to hold values
private int[] a = new int[100];
private int[] b = new int[100];

// number of elements in array
private int x;

// Merge Sort Algorithm
public void sortArray()
{
m_sort( 0, x-1 );
}

public void m_sort( int left, int right )
{
int mid;

if( right > left )
{
mid = ( right + left ) / 2;
m_sort( left, mid );
m_sort( mid+1, right );

merge( left, mid+1, right );
}
}

public void merge( int left, int mid, int right )
{
int i, left_end, num_elements, tmp_pos;

left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;

while( (left <= left_end) && (mid <= right) )
{
if( a <= a[mid] )
{
b[tmp_pos] = a;
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
b[tmp_pos] = a[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}

while( left <= left_end )
{
b[tmp_pos] = a;
left = left + 1;
tmp_pos = tmp_pos + 1;
}

while( mid <= right )
{
b[tmp_pos] = a[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}

for( i = 0; i < num_elements; i++ )
{
a = b;
right = right - 1;
}
}

Thank you, but it is 2 way sorting. I need to modify my algorithm to become n-way merge sort.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.