## MergeSort alogorithm

Category : Data-structures-algorithms | Sub Category : MergeSort alogorithm | By Prasad Bonam Last updated: 2023-07-10 10:11:04 Viewed : 67

MergeSort alogorithm:

Here is an example of the MergeSort algorithm implemented in Java:

```javapublic class MergeSort {

public static void mergeSort(int[] arr) {
mergeSort(arr, 0, arr.length - 1);
}

private static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}

private static void merge(int[] arr, int left, int mid, int right) {
int leftSize = mid - left + 1;
int rightSize = right - mid;

int[] leftArr = new int[leftSize];
int[] rightArr = new int[rightSize];

// Copy data to temporary arrays
System.arraycopy(arr, left, leftArr, 0, leftSize);
System.arraycopy(arr, mid + 1, rightArr, 0, rightSize);

int i = 0, j = 0, k = left;

// Merge the temporary arrays back into arr
while (i < leftSize && j < rightSize) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}

// Copy the remaining elements of leftArr, if any
while (i < leftSize) {
arr[k++] = leftArr[i++];
}

// Copy the remaining elements of rightArr, if any
while (j < rightSize) {
arr[k++] = rightArr[j++];
}
}

public static void main(String[] args) {
int[] arr = { 8, 5, 2, 9, 1, 6, 3, 7 };
System.out.println("Original array: " + Arrays.toString(arr));

mergeSort(arr);

System.out.println("Sorted array: " + Arrays.toString(arr));
}
}```

In the `mergeSort` method, we define the base case where the `left` index is less than the `right` index. If the base case is satisfied, we calculate the middle index (`mid`) and recursively call `mergeSort` for the left and right halves of the array. Finally, we merge the two sorted halves using the `merge` method.

The `merge` method takes the left, middle, and right indices as parameters. It creates temporary arrays (`leftArr` and `rightArr`) to store the values of the left and right halves of the array. Then, it iterates over both halves, comparing the elements and merging them back into the original array in sorted order.

In the `main` method, we demonstrate the usage of the MergeSort algorithm by sorting an example array. The original array is printed before sorting, and the sorted array is printed afterward.

The MergeSort algorithm has a time complexity of O(n log n) and performs stable sorting.