For learning purposes, I decided to look at the merge sorting algorithm, the implementation algorithm is quite understandable, but with the implementation itself it did not work, I found an example on the Internet:

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++; } } } }

in principle, everything seems to be clear, except for one thing, why the following is done in the Merge method:

  leftArray[lengthLeft] = int.MaxValue; rightArrray[lengthRight] = int.MaxValue;

    1 answer 1

    I will answer a little simplified. It will consider that all our sorted elements are strictly less than int.MaxValue .

    We should not take elements with an index larger than the size of the array. This is usually done by changing the if(leftArray[iIndex] <= rightArrray[jIndex]) to if(jIndex==rightArrray.size() || leftArray[iIndex] <= rightArrray[jIndex]) but for simplicity you can use the above method . Then the most extreme element of the array will be more than all the others and therefore will never be selected.