Merge sort is a popular sorting algorithm known for its efficiency and stability. It follows the divide-and-conquer strategy, where the array to be sorted is recursively divided into smaller subarrays until they are trivially sorted, and then the subarrays are merged back together in a sorted manner.
Here’s a high-level explanation of the merge sort algorithm:
1. Divide: The unsorted array is divided into two halves recursively until each half contains only one element (trivially sorted).
2. Conquer: Once the array is divided into single-element halves, they are merged back together in a sorted manner.
3. Merge: During the merge step, the two smaller sorted arrays are combined into a single sorted array. This is done by comparing the elements from each array and selecting the smaller one to place into the merged array. This process continues until all elements from both arrays are included in the merged array.
Here’s a simple implementation of merge sort in Java:
import java.util.Arrays;
public class MergeSortExample {
public static void mergeSort(int[] arr) {
if (arr.length <= 1) {
return;
}
int mid = arr.length / 2;
int[] left = Arrays.copyOfRange(arr, 0, mid);
int[] right = Arrays.copyOfRange(arr, mid, arr.length);
mergeSort(left);
mergeSort(right);
merge(arr, left, right);
}
public 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++];
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
System.out.println("Original array: " + Arrays.toString(arr));
mergeSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}
In this implementation:
– `mergeSort` is the main method that sorts the array using merge sort.
– `merge` is a helper method that merges two sorted arrays into one sorted array.
This implementation demonstrates the basic idea behind merge sort. It recursively divides the array into smaller halves until they are trivially sorted (single-element arrays), and then merges them back together in sorted order.