How to write a Java program that illustrates merge sort?
Merge Sort is a well-known and effective sorting method that divides a problem into numerous smaller problems using the divide and conquer technique. It divides the supplied array into two more equal halves until the size of succeeding halves equals 1, at which point it makes calls for the two halves and joins the two sorted halves.
Implementation of merge sort
- #include <stdio.h>
- /* Function to merge the subarrays of a[] */
- void merge(int a[], int beg, int mid, int end)
- {
- int i, j, k;
- int n1 = mid – beg + 1;
- int n2 = end – mid;
- int LeftArray[n1], RightArray[n2]; //temporary arrays.
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.
Merge Sort is a well-known and effective sorting method that divides a problem into numerous smaller problems using the divide and conquer technique. It divides the supplied array into two more equal halves until the size of succeeding halves equals 1, at which point it makes calls for the two halves and joins the two sorted halves.
Implementation of merge sort
- #include <stdio.h>
- /* Function to merge the subarrays of a[] */
- void merge(int a[], int beg, int mid, int end)
- {
- int i, j, k;
- int n1 = mid – beg + 1;
- int n2 = end – mid;
- int LeftArray[n1], RightArray[n2]; //temporary arrays.