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

[blackbanny]

проблема с рекурсивной сортировкой слиянием, ума не приложу в чем дело...

template <class T> void vector<T>::Start_Merge_Sort()
{
   T* arraytemp;                 //вспомогательный массив
   arraytemp = new T[size];
   Merge_Sort(0, size-1, arraytemp);
   delete[] arraytemp;
  
}
//рекурсивная сортировка слиянием
template <class T> void vector<T>::Merge_Sort(int l, int r, T *arraytemp)
{
  if(r <= l) return;

  int m = (l + r)/2;
  Merge_Sort(l, m, arraytemp);
  Merge_Sort(m+1, r, arraytemp);
  Merge(l, r, m, arraytemp);
}
//вспомогательная функция Merge
template <class T> void vector<T>::Merge(int l, int r, int m, T *arraytemp)
{
int i, j;

   for(i = m + 1; i >= l + 1; i--)
   {
	   arraytemp[i-1] = array[i-1];
   }
   for(j = m; j < r - 1; j++)
   {
	   arraytemp[r+m-j] = array[j+1];
   }
   for(int k = l; k < r; k++)
   {
	   if(arraytemp[j] <= arraytemp[i])
	   {
		   array[k] = arraytemp[j];
		   j = j - 1;
	   }else
	   {
		   array[k] = arraytemp[i];
		   i = i + 1;
	   }

   }
}

[blackbanny]

псевдокод брал отсюда

телепатов здесь нет

какая проблема?

[blackbanny]

телепатов здесь нет

какая проблема?

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

1-й раз:
до сортировки: 95 3 3 54 13 72
после сортировки: 3 54 54 3 95 72(здесь 13 куда то пропала)

2-й раз:
до сортировки: 51 54 16 62 53 10
после сортировки: 51 54 16 62 62 10(здесь 53 куда то пропала)

3-й раз:
до сортировки: 74 0 1 86 95 95
после сортировки: 0 74 1 86 95 95

он вроде как сортирует парно, но потом отсортированные пары не сортирует или что, ниче понять не могу...

[MBo]

При слиянии нужно учитывать то, что один из подмассивов может закончиться раньше.

[blackbanny]

MBo,а можешь указать в коде ошибку?

здесь:

Код:

for(int k = l; k < r; k++) { if(arraytemp[j] <= arraytemp[i]) { array[k] = arraytemp[j]; j = j - 1; }else { array[k] = arraytemp[i]; i = i + 1; } }

[blackbanny]

При слиянии нужно учитывать то, что один из подмассивов может закончиться раньше.

можете подробнее пояснить? что значит может закончиться раньше?

j у тебя может стать меньше m, или i больше m
отсюда проблемы особенно когда размер массива 1-2 элемента

[blackbanny]

j у тебя может стать меньше m, или i больше m
отсюда проблемы особенно когда размер массива 1-2 элемента

т.е. надо надо написать:

   if(j < m || i > m) return;
   for(int k = l; k < r; k++)
   {
	   if(arraytemp[j] <= arraytemp[i])
	   {
		   array[k] = arraytemp[j];
		   j = j - 1;
	   }else
	   {
		   array[k] = arraytemp[i];
		   i = i + 1;
	   }

   }

но от этого ничего не меняется...