public class MergeSort {
public static void main(String[] args) {
int[] arr = {5, 2, 8, 1, 3};
System.out.println("Before sorting:");
printArray(arr);
mergeSort(arr, 0, arr.length - 1);
System.out.println("After sorting:");
printArray(arr);
}
public static void mergeSort(int[] arr, int start, int end) {
if (start < end) {
int mid = (start + end) / 2;
mergeSort(arr, start, mid);
mergeSort(arr, mid + 1, end);
merge(arr, start, mid, end);
}
}
public static void merge(int[] arr, int start, int mid, int end) {
int n1 = mid - start + 1;
int n2 = end - mid;
int[] left = new int[n1];
int[] right = new int[n2];
for (int i = 0; i < n1; i++) {
left[i] = arr[start + i];
}
for (int i = 0; i < n2; i++) {
right[i] = arr[mid + 1 + i];
}
int i = 0, j = 0, k = start;
while (i < n1 && j < n2) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < n1) {
arr[k++] = left[i++];
}
while (j < n2) {
arr[k++] = right[j++];
}
}
public static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
Before sorting:5 2 8 1 3
After sorting:
1 2 3 5 8
arr
and initialize it with the values 5, 2, 8, 1, and 3. We then print the array before sorting using the printArray
method.mergeSort
method and pass the array, the start index (0), and the end index (length - 1) as arguments. This method recursively divides the array into two halves until each half contains only one element, then merges the two halves into a sorted array using the merge
method.merge
method takes the array, the start index of the first half, the end index of the first half (which is also the mid index of the original array), and the end index of the second half as arguments. It first creates two new arrays to store the elements of each half, then copies the elements from the original array into the two new arrays. It then merges the two arrays into a sorted array by comparing the first elements of each array, and copying the smaller element into the original array. It repeats this process until all elements have been copied into the original array.printArray
method.