Void SortM(int start, int finish, int[] temp)

{

if (start < finish)

{

int mid = (start + finish) / 2;

SortM(start, mid, temp);

SortM(mid + 1, finish, temp);

Merge(start, mid, finish, temp);

}

}

/// <summary>

/// Слияние отсортированных частей масссива в массив temp

/// После слияния массив переписывается в исходный массив

/// </summary>

/// <param name="start">начало первой части</param>

/// <param name="mid">конец первой части - начало второй</param>

/// <param name="finish">конец второй части</param>

/// <param name="temp">временный массив с результатами слияния</param>

///

Void Merge(int start, int mid, int finish, int[] temp)

{

int topl = start, topr = mid + 1, topt =start;

//Слияние, пока не завершится одна из частей массива

while ((topl <= mid) && (topr <= finish))

{

if (arr[topl] <= arr[topr])

temp[topt++] = arr[topl++];

else

temp[topt++] = arr[topr++];

}

//дописывание остатка незавершенной части массива

while (topl <= mid)

temp[topt++] = arr[topl++];

while (topr <= finish)

temp[topt++] = arr[topr++];

//переливаем элементы в исходный массив

for (int i = start; i <= finish; i++)

arr[i] = temp[i];

}

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

/// <summary>

/// Поиск за линейное время(в среднем) квантили

/// массива порядка k.

/// При k = n/2 квантиль задает медиану массива.

/// </summary>

/// <param name="k">порядок квантили</param>

/// <returns> квантиль порядка k</returns>

public int Find(int k)

{

int l = 0, r = n - 1;

int x = 0;

while (l < r)

{

x = arr[k]; //барьер

//Разбиение на два подмножества

int i = l, j = r;

do

{

while (arr[i] < x) i++;

while (x < arr[j]) j--;

if (i <= j)

{

if (arr[i] != arr[j])

{//обмен

int w = arr[i]; arr[i] = arr[j]; arr[j] = w;

}

i++; j--;

}

}

while (i <= j);

//Изменение границ интервала поиска

if (j < k) l = i;

if(k < i) r = j;

}

return (arr[k]);

}

Закончим рассмотрение методов класса специальным методом, позволяющим вычислить время, затрачиваемое на сортировку массива:

/// <summary>

/// Подсчет времени сортировки

/// Сортируется один и тот же массив 10000 раз

/// Метод сортировки передается как параметр

/// </summary>

/// <param name="sort">Метод сортировки</param>

/// <returns> время сортировки </returns>

public int HowLong(SortMethod sort)

{

const int count = 10000;

Int start, finish;

start = MS(DateTime.Now);

for (int i = 1; i <= count; i++)

{

Random rnd = new Random(77);

for (int j = 0; j < n; j++)

{

arr[j] = rnd.Next(-1000,1000);

}

sort();

}

finish = MS(DateTime.Now);

return (finish - start);

}//HowLong