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){
                    arrSortedInt.Add(rightArray[rightptr]);
                    rightptr++;
                }else if (rightptr==rightArray.Count){
                    arrSortedInt.Add(leftArray[leftptr]);
                    leftptr++;
                }else if ((int)leftArray[leftptr]<(int)rightArray[rightptr]){
                    //need the cast above since arraylist returns Type object
                    arrSortedInt.Add(leftArray[leftptr]);
                    leftptr++;
                }else{
                    arrSortedInt.Add(rightArray[rightptr]);
                    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.

This article has been dead for over six months. Start a new discussion instead.