To understand the above Java program to sort an array of given integers using Merge sort Algorithm, we need to understand what is merge sort.
Merge sort is an O (n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output.
Conceptually, a merge sort works as follows :
• Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
• Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.
import java.util.Arrays;
class MergeSort
{
void merge(int nums[], int left, int m, int right)
{
int n1 = m - left + 1;
int n2 = right - m;
int Left_part_arra[] = new int [n1];
int Right_part_arra[] = new int [n2];
for (int i=0; i<n1; ++i)
Left_part_arra[i] = nums[left + i];
for (int j=0; j<n2; ++j)
Right_part_arra[j] = nums[m + 1+ j];
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2)
{
if (Left_part_arra[i] <= Right_part_arra[j])
{
nums[k] = Left_part_arra[i];
i++;
}
else
{
nums[k] = Right_part_arra[j];
j++;
}
k++;
}
while (i < n1)
{
nums[k] = Left_part_arra[i];
i++;
k++;
}
while (j < n2)
{
nums[k] = Right_part_arra[j];
j++;
k++;
}
}
// merge()
void sort(int nums[], int left, int right)
{
if (left < right)
{
// Find the middle point
int m = (left+right)/2;
// Sort first halve
sort(nums, left, m);
// Sort second halve
sort(nums , m+1, right);
// Merge the sorted halves
merge(nums, left, m, right);
}
}
// Method to test above
public static void main(String args[])
{
MergeSort ob = new MergeSort();
int nums[] = {6, 3, -9, 10, 52, 36 ,0, -2};
System.out.println("Original Array:");
System.out.println(Arrays.toString(nums));
ob.sort(nums, 0, nums.length-1);
System.out.println("Sorted Array:");
System.out.println(Arrays.toString(nums));
}
}
Sample Output: Original Array: [6, 3, -9, 10, 52, 36, 0, -2] Sorted Array: [-9, -2, 0, 3, 6, 10, 36, 52]