Using the merge sort method ,arrange the given inputs:
Inputs:
12 11 13 5 6 7
Output:
5 6 7 11 12 13
package sorting;
public class MergeSort {
// Helper method to print the array
// Main method
public static void main(String[] args) {
int[] array = {12, 11, 13, 5, 6, 7};
System.out.println("Given Array");
printArray(array);
//calling the mergesort method
mergeSort(array, 0, array.length - 1);
//printing the merged array
System.out.println("\nSorted array");
printArray(array);
}
// Main function that sorts array[left...right] using merge()
public static void mergeSort(int[] array, int left, int right) {
if (left < right) {
// Find the middle point
int middle = left + (right - left) / 2;
// Sort first and second halves
mergeSort(array, left, middle);
mergeSort(array, middle + 1, right);
// Merge the sorted halves
merge(array, left, middle, right);
}
}
public static void merge(int[] array, int left, int middle, int right) {
//Finding the length for left and right array
int n1 = middle - left + 1;
int n2 = right - middle;
//Creating left and right array
int[] leftArray = new int[n1];
int[] rightArray = new int[n2];
//Assigning the value to the left and right arrays
for (int i = 0; i < n1; ++i)
leftArray[i] = array[left + i];
for (int j = 0; j < n2; ++j)
rightArray[j] = array[middle + 1 + j];
//initializing the index values for the arrays
int i = 0, j = 0;
int k = left;
//sorting the arrays with more than value
while (i < n1 && j < n2) {
if (leftArray[i] <= rightArray[j]) {
array[k] = leftArray[i];
i++;
} else {
array[k] = rightArray[j];
j++;
}
k++;
}
//sorting the array with only one value
while (i < n1) {
array[k] = leftArray[i];
i++;
k++;
}
while (j < n2) {
array[k] = rightArray[j];
j++;
k++;
}
}
//printing the array
public static void printArray(int[] array) {
int n = array.length;
for (int i = 0; i < n; ++i)
System.out.print(array[i] + " ");
System.out.println();
}
}