- The `MergeSort` function first checks if the array is of length 1 or less. If so, it returns because the array is already sorted.
- It then divides the array into two halves: `left` and `right`.
- It recursively sorts both halves using `MergeSort`.
- After sorting both halves, it merges them together in sorted order using the `Merge` function.
The `Merge` function takes in the main array and its two halves. It then merges the two halves back into the main array in sorted order.
public static void MergeSort(int[] arr) {
if (arr.Length <= 1) {
return;
}
int mid = arr.Length / 2;
int[] left = new int[mid];
int[] right = new int[arr.Length - mid];
for (int i = 0; i < mid; i++) {
left[i] = arr[i];
}
for (int i = mid; i < arr.Length; i++) {
right[i - mid] = arr[i];
}
MergeSort(left);
MergeSort(right);
Merge(arr, left, right);
}
private static void Merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
while (i < left.Length && j < right.Length) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < left.Length) {
arr[k++] = left[i++];
}
while (j < right.Length) {
arr[k++] = right[j++];
}
}
```