Рекурсивная сортировка слиянием

[Smitt&Wesson]

Сортирует массив используя рекурсивную сортировку слиянием
https://ru.wikipedia.org/wiki/Сортировка_слиянием
up - указатель на массив который нужно сортировать
down - указатель на массив с, как минимум, таким же размерои как у 'up', используется как буфер
left - левая граница массива, передайте 0 чтобы сортировать массив с начала
right - правая граница массива, передайте длинну массива - x чтобы сортировать массив до последнего элемента
возвращает: указатель на отсортированный массив. Из за особенностей работы
данной имплементации, отсортированная версия массива может оказаться либо в 'up' либо в 'down'

#include<iostream.h>
#include<stdlib>
using namespace std;

void Print(int *arr, int x)
{
  for(int i = 0; i < x; i++) cout << arr[i] << "  ";
  cout << "\n";
}

int* MergeSort(int *up, int *down, unsigned int left, unsigned int right)
{
  if (left == right)
  {
    down[left] = up[left];
    return down;
  }
  unsigned int middle = (unsigned int)((left + right)/2);// * 0.5f);
  // разделяй и сортируй
  int *l_buff = MergeSort(up, down, left, middle);
  int *r_buff = MergeSort(up, down, middle + 1, right);

  // слияние двух отсортированных половин
  int *target = l_buff == up ? down : up;

  unsigned int l_cur = left, r_cur = middle + 1;
  for (unsigned int i = left; i <= right; i++)
  {
    if (l_cur <= middle && r_cur <= right)
    {
      if (l_buff[l_cur] < r_buff[r_cur])
      {
        target[i] = l_buff[l_cur];
        l_cur++;
      }
      else
      {
        target[i] = r_buff[r_cur];
        r_cur++;
      }
    }
    else if (l_cur <= middle)
    {
      target[i] = l_buff[l_cur];
      l_cur++;
    }
    else
    {
      target[i] = r_buff[r_cur];
      r_cur++;
    }
  }
cout << "target  "; Print(target, middle);
//  cout << "l_buff  "; Print(l_buff, middle);
//  cout << "r_buff  "; Print(r_buff, middle);
  return target;
}

//----------------------------------------------

int main()
{
  cout << "рекурсивная сортировка слиянием. ";
  int x = 10;
  int *iarr = new int[x];
  iarr[0] = 63; iarr[1] = 64; iarr[2] = 5; iarr[3] = 65; iarr[4] = 50;
  iarr[5] = 62; iarr[6] = 53; iarr[7] = 54; iarr[8] = 60; iarr[9] = 61;
  int *buf = new int[x];
  int *rez = new int[x];
  rez = MergeSort(iarr, buf, 0, x);
  if(x <= 100) Print(rez, x+1);
  cout << "\n\n";

  delete iarr;

  system("pause");
  return 0;
}

Проблема в том, что алгоритм почему-то вставляет в отсортированную последовательность цифру, нигде в массиве не заданную. Если при выводе задать размер массива на единицу больше, за лишней цифрой оказывается нормально отсортированная последовательность.
Третий день голову ломаю, не могу понять в чём причина.

[waleri]

Выход за границу массива.
При первоначальном вызове MergeSort последний аргумент - количество элементов (10) а должен быть индекс последнего элемента (9)

[Smitt&Wesson]

Сообщение от waleri

Выход за границу массива.
При первоначальном вызове MergeSort последний аргумент - количество элементов (10) а должен быть индекс последнего элемента (9)

Ну, это я давно уже понял (отладчиком умею пользоваться). Вопрос в том, как это устранить не нарушая работу всего алгоритма? Статья в Вики, откуда я эту прогу слизал, ответов на этот вопрос не даёт.

Ответ нашел. При вызове функции нужно задавать значение x-1.
rez = MergeSort(iarr, buf, 0, x-1);

[evg_m]

на входе (left перый сортируемый \right первый НЕсортируемый (следующий за последним!!)
на промежуточных

left первый сортируемый \ middle последний СОРТИРУЕМЫЙ 
midle+1 первый сортируемый    \ right первый НЕ сортируемый

РАЗНАЯ интерпретация параметра right !!!!

left первый сортируемый  \ middle первый НЕ сортируемый
middle  первый Сортируемый  \ right первый НЕ сортируемый

Условие выхода из рекурсии right (первый НЕсортируемый) - left (первый сортируемый) == 1

Ответ нашел. При вызове функции нужно задавать значение x-1.

Или сменить входную интерпретацию (последний сортируемый)

[Smitt&Wesson]

Или сменить входную интерпретацию (последний сортируемый)

Рекурсивная сортировеа Qsort, работает точно так же. При её вызове размер массива задаётся как x-1. Так, что это не принципиально.