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

Решил в целях обучения посмотреть алгоритм сортировки слиянием, алгоритм реализации вполне понятен, а вот с самой реализацией - не получилось, на просторах интернета нашел вот такой пример:
public void StartMethod() { Random rnd = new Random(); int[] unsortedArray = new int[85]; for(var i = 0; i < unsortedArray.Length; i ++) { unsortedArray[i] = rnd.Next(1, 100); } MergeSort(unsortedArray, 1, unsortedArray.Length - 1); foreach(int element in unsortedArray) { Console.WriteLine(element); } }
private void MergeSort(int[] unsortedArray, int leftIndex, int rightIndex) {
if(leftIndex < rightIndex) { int middleIndex = (leftIndex + rightIndex) / 2; MergeSort(unsortedArray, leftIndex, middleIndex); MergeSort(unsortedArray, middleIndex + 1, rightIndex); Merge(unsortedArray, leftIndex, middleIndex, rightIndex); } }
private void Merge(int[] unsortedArray, int leftIndex, int middleIndex, int rightIndex) { int lengthLeft = middleIndex - leftIndex + 1; int lengthRight = rightIndex - middleIndex; int[] leftArray = new int[lengthLeft + 1]; int[] rightArrray = new int[lengthRight + 1]; for(int i = 0; i < lengthLeft; i ++) { leftArray[i] = unsortedArray[leftIndex + i]; } for(int j =0; j < lengthRight; j++) { rightArrray[j] = unsortedArray[middleIndex + j + 1]; }
leftArray[lengthLeft] = int.MaxValue; rightArrray[lengthRight] = int.MaxValue;
int iIndex = 0; int jIndex = 0;
for (int k = leftIndex; k <= rightIndex; k ++) { if(leftArray[iIndex] <= rightArrray[jIndex]) { unsortedArray[k] = leftArray[iIndex]; iIndex++; } else { unsortedArray[k] = rightArrray[jIndex]; jIndex++; } } } }
в принципе вроде все понятно за исключением одного момента,зачем в методе Merge делается следующее:
leftArray[lengthLeft] = int.MaxValue; rightArrray[lengthRight] = int.MaxValue;

Ответ

Отвечу чуть упрощённо. Будет считать что все наши сортируемые элементы строго меньше чем int.MaxValue.
Мы не должны брать элементы с индексом большим, чем размер массива. Обычно это делается изменением компаратора if(leftArray[iIndex] <= rightArrray[jIndex]) на if(jIndex==rightArrray.size() || leftArray[iIndex] <= rightArrray[jIndex]) но для простоты можно использовать метод как выше. Тогда самый крайний элемент массива будет больше всех остальных и следовательно никогда не будет выбран.