Проблема сортировки слиянием

Question

Я составляю меню всех видов алгоритма сортировки, и теперь я застрял в сортировке слиянием. Я столкнулся с ошибкой после нажатия кнопки выполнить. Я ввел 5 чисел в TextBox1 и еще один набор из 5 чисел в TextBox2. Это говорит, что индекс был вне границ массива. Я указал на коды, где он появился. Есть идеи, в чем проблема?

    private void ExeButton_Click(object sender, EventArgs e)
    {
        string[] numsInString = EntNum.Text.Split(' ');   //split values in textbox
        string[] numsInString1 = EntNum1.Text.Split(' ');
        for (int j = 0; j < numsInString.Length; j++)
        {
            a[j] = int.Parse(numsInString[j]);
        }
        for (int j = 0; j < numsInString1.Length; j++)
        {
            b[j] = int.Parse(numsInString1[j]);
        }
        {
            sortArray();
            Display();
        }

    }

    public void sortArray()
    {
        m_sort(0, 10 - 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[left] <= a[mid])  //index was outside the bounds of the the array
            {
                b[tmp_pos] = a[left];
                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 = 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[right] = b[right];
            right = right - 1;
        }
    }


    private void ClearButton_Click(object sender, EventArgs e)
    {
        richTextBox1.Clear();
    }

    public void Display()
    {
        int i;
        String numbers = "";
        for (i = 0; i < 10; i++)
        numbers += a[i].ToString() + "       ";
        numbers += b[i].ToString() + "       ";
        richTextBox1.AppendText(numbers + "\n");
    }

Answer 1

Относительно вашего конкретного вопроса: a - это массив из 5 элементов с индексами 0, 1, 2, 3, 4, поэтому a[4] - последний элемент.Вы начинаете с m_sort(0, 10 - 1) = m_sort(0, 9);.В m_sort() вы вычисляете

mid = (right + left) / 2 = (9 + 0) / 2 = 4

и звоните

merge(left, mid + 1, right) = merge(0, 4 + 1, 9) = merge(0, 5, 9).

В merge(int left, int mid, int right) вы оцениваете:

if (a[left] <= a[mid])   i.e.     if (a[0] <= a[5]) 

, поэтому вы получаете доступ к a[5], которыйвне границ.

Я думаю, что ваша сортировка слиянием может быть значительно упрощена.Вы можете посмотреть на многочисленные ресурсы в Интернете или в учебнике по алгоритмам.

Answer 2

Вот пример способа упростить слияние, предполагая, что каждый список отсортирован с элементом 0, имеющим самое высокое значение:

int c[] = new int[a.Length + b.Length];
int aPos = 0;
int bPos = 0;

for(int i = 0; i < c.Length; i++)
{
    if(a[APos] > b[bPos])
    {
        c[i] = a[Apos];
        if(aPos < aPos.Length - 1)
            aPos++;
    }
    else
    {
        c[i] = b[bPos];
        if(bPos < bPos.Length - 1)
            bPos++;
    }
}

Answer 3

// 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[left] <= a[mid] )
    {
      b[tmp_pos] = a[left];
      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 = 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[right] = b[right];
    right = right - 1;
  }
}