How to write a Java program that illustrates merge sort?
Sure! Here’s an example of a Java program that implements the merge sort algorithm:
<span class="hljs-keyword">public</span> <span class="hljs-keyword">class</span> <span class="hljs-title class_">MergeSortExample</span> {
<span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title function_">main</span><span class="hljs-params">(String[] args)</span> {
<span class="hljs-type">int</span>[] array = {<span class="hljs-number">5</span>, <span class="hljs-number">3</span>, <span class="hljs-number">8</span>, <span class="hljs-number">6</span>, <span class="hljs-number">2</span>, <span class="hljs-number">7</span>, <span class="hljs-number">1</span>, <span class="hljs-number">4</span>};
System.out.println(<span class="hljs-string">"Array before sorting:"</span>);
printArray(array);
mergeSort(array, <span class="hljs-number">0</span>, array.length - <span class="hljs-number">1</span>);
System.out.println(<span class="hljs-string">"Array after sorting:"</span>);
printArray(array);
}
<span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title function_">mergeSort</span><span class="hljs-params">(<span class="hljs-type">int</span>[] array, <span class="hljs-type">int</span> left, <span class="hljs-type">int</span> right)</span> {
<span class="hljs-keyword">if</span> (left < right) {
<span class="hljs-type">int</span> <span class="hljs-variable">middle</span> <span class="hljs-operator">=</span> (left + right) / <span class="hljs-number">2</span>;
mergeSort(array, left, middle);
mergeSort(array, middle + <span class="hljs-number">1</span>, right);
merge(array, left, middle, right);
}
}
<span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title function_">merge</span><span class="hljs-params">(<span class="hljs-type">int</span>[] array, <span class="hljs-type">int</span> left, <span class="hljs-type">int</span> middle, <span class="hljs-type">int</span> right)</span> {
<span class="hljs-type">int</span> <span class="hljs-variable">n1</span> <span class="hljs-operator">=</span> middle - left + <span class="hljs-number">1</span>;
<span class="hljs-type">int</span> <span class="hljs-variable">n2</span> <span class="hljs-operator">=</span> right - middle;
<span class="hljs-type">int</span>[] leftArray = <span class="hljs-keyword">new</span> <span class="hljs-title class_">int</span>[n1];
<span class="hljs-type">int</span>[] rightArray = <span class="hljs-keyword">new</span> <span class="hljs-title class_">int</span>[n2];
<span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> <span class="hljs-variable">i</span> <span class="hljs-operator">=</span> <span class="hljs-number">0</span>; i < n1; i++) {
leftArray[i] = array[left + i];
}
<span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> <span class="hljs-variable">j</span> <span class="hljs-operator">=</span> <span class="hljs-number">0</span>; j < n2; j++) {
rightArray[j] = array[middle + <span class="hljs-number">1</span> + j];
}
<span class="hljs-type">int</span> <span class="hljs-variable">i</span> <span class="hljs-operator">=</span> <span class="hljs-number">0</span>, j = <span class="hljs-number">0</span>;
<span class="hljs-type">int</span> <span class="hljs-variable">k</span> <span class="hljs-operator">=</span> left;
<span class="hljs-keyword">while</span> (i < n1 && j < n2) {
<span class="hljs-keyword">if</span> (leftArray[i] <= rightArray[j]) {
array[k] = leftArray[i];
i++;
} <span class="hljs-keyword">else</span> {
array[k] = rightArray[j];
j++;
}
k++;
}
<span class="hljs-keyword">while</span> (i < n1) {
array[k] = leftArray[i];
i++;
k++;
}
<span class="hljs-keyword">while</span> (j < n2) {
array[k] = rightArray[j];
j++;
k++;
}
}
<span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title function_">printArray</span><span class="hljs-params">(<span class="hljs-type">int</span>[] array)</span> {
<span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> value : array) {
System.out.print(value + <span class="hljs-string">" "</span>);
}
System.out.println();
}
}
In this program, the mergeSort method is the main entry point for the merge sort algorithm. It takes an array, the left index, and the right index as parameters. It recursively divides the array into smaller subarrays until each subarray has only one element. Then it merges the subarrays back together in sorted order using the merge method.
The merge method takes the array and the indices of the left, middle, and right subarrays as parameters. It creates temporary arrays to hold the left and right subarrays, then compares the elements from the subarrays one by one and merges them back into the original array in sorted order.
The printArray method is a helper method used to print the elements of the array.
When you run this program, it will sort the array {5, 3, 8, 6, 2, 7, 1, 4} using the merge sort algorithm and print the sorted array.