Member Avatar for amadaeliseo

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.

  • 2 Contributors
  • 2 Replies
  • 129 Views
  • 7 Hours Discussion Span
  • Latest Post Latest Post by amadaeliseo

Dani AI

Generated

The code you posted (and 's example) is the standard two-way divide-and-conquer merge. To generalize to n-way (k-way) merge sort: split the input into k roughly equal sublists, recursively sort each sublist, then perform a k-way merge of the k sorted runs. The efficient way to do that merge is a min-heap (priority queue) that holds the current head of each run — each extract gives the next smallest element and you then push the next element from that run. The merge step is O(n log k); with heap-based merging across the recursion the overall work stays O(n log n) but you reduce recursion depth.

A compact C# implementation idea (uses List<int> and the .NET PriorityQueue available in .NET 6+):

public static List<int> KWayMergeSort(List<int> arr, int k)
{
    if (arr == null) throw new ArgumentNullException(nameof(arr));
    if (arr.Count <= 1 || k <= 1) return new List<int>(arr);

    int n = arr.Count;
    var parts = new List<List<int>>();
    int baseSize = n / k;
    int rem = n % k;
    int start = 0;
    for (int i = 0; i < k && start < n; i++)
    {
        int size = baseSize + (i < rem ? 1 : 0);
        parts.Add(arr.GetRange(start, size));
        start += size;
    }

    for (int i = 0; i < parts.Count; i++)
        parts[i] = KWayMergeSort(parts[i], k);

    var pq = new PriorityQueue<(int value, int listIdx, int idx), int>();
    for (int i = 0; i < parts.Count; i++)
        if (parts[i].Count > 0) pq.Enqueue((parts[i][0], i, 0), parts[i][0]);

    var result = new List<int>(n);
    while (pq.Count > 0)
    {
        var top = pq.Dequeue();
        result.Add(top.value);
        int next = top.idx + 1;
        if (next < parts[top.listIdx].Count)
            pq.Enqueue((parts[top.listIdx][next], top.listIdx, next), parts[top.listIdx][next]);
    }

    return result;
}

Practical notes: prefer generic List<T> over ArrayList to avoid boxing/unboxing and casts; preallocate result capacity to reduce reallocations; splitting with GetRange copies memory — for large inputs consider passing index ranges instead of making many small lists. PriorityQueue<TElement,TPriority> is in modern .NET; on older frameworks implement a small binary heap or use a SortedSet workaround. Choosing k trades off heap overhead vs recursion depth — for in-memory sorts k of 3..8 is common; for external sorting you use k to match available streams.

Relevant references: Microsoft docs for PriorityQueue<TElement,TPriority> and List<T>.

Recommended Answers

All 2 Replies

Member Avatar for IdanS

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;
  }
}
Member Avatar for amadaeliseo

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.