Void Swap(T[] items, int left, int right)

Сортировка слиянием
При сортировке слиянием мы разделяем массив пополам до тех пор, пока каждый участок не станет длиной в один элемент. Затем эти участки возвращаются на место (сливаются) в правильном порядке.
Давайте посмотрим на такой массив:

Разделим его пополам:

И будем делить каждую часть пополам, пока не останутся части с одним элементом:

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

Сначала мы получаем группы по два отсортированных элемента, потом «собираем» их в группы по четыре элемента и в конце собираем все вместе в отсортированный массив.

Для работы алгоритма мы должны реализовать следующие операции:

1. 
   Операцию для рекурсивного разделения массива на группы (метод Sort).
   
2. 
   Слияние в правильном порядке (метод Merge).
   

Стоит отметить, что в отличие от линейных алгоритмов сортировки, сортировка слиянием будет делить и склеивать массив вне зависимости от того, был он отсортирован изначально или нет. Поэтому, несмотря на то, что в худшем случае он отработает быстрее, чем линейный, в лучшем случае его производительность будет ниже, чем у линейного. Поэтому сортировка слиянием — не самое лучшее решение, когда надо отсортировать частично упорядоченный массив.
public void Sort(T[] items)
{
if (items.Length <= 1)
{
return;
}

int leftSize = items.Length / 2;

int rightSize = items.Length - leftSize;
T[] left = new T[leftSize];
T[] right = new T[rightSize];
Array.Copy(items, 0, left, 0, leftSize);
Array.Copy(items, leftSize, right, 0, rightSize);
Sort(left);
Sort(right);
Merge(items, left, right);
}

private void Merge(T[] items, T[] left, T[] right)

{
int leftIndex = 0;
int rightIndex = 0;
int targetIndex = 0;
int remaining = left.Length + right.Length;
while(remaining > 0)
{
if (leftIndex >= left.Length)
{
items[targetIndex] = right[rightIndex++];
}
else if (rightIndex >= right.Length)
{
items[targetIndex] = left[leftIndex++];
}
else if (left[leftIndex].CompareTo(right[rightIndex]) < 0)
{
items[targetIndex] = left[leftIndex++];
}
else
{
items[targetIndex] = right[rightIndex++];
}

targetIndex++;

remaining--;
}
}