MergeSort In Java
June 23, 2017
Categorised in: Java Codes
- Uses Divide and Conquer strategy like QuickSort.
- It divides the array of numbers into sub-arrays (from middle) until there is only one element in each sub-array.
- These sub-arrays are then merged into sorted sub-arrays until we obtain a sorted merged array.
- Stable
- Best Case Time Complexity: O(n log n)
- Worst Case Time Complexity: O(n log n)
- Space Complexity: O(n)
public class MergeSortInJava
{
void sort(int arr[], int l, int r)
{
if (l < r)
{
// Find mid
int m = (l+r)/2;
// Sort first and second halves with recursion
sort(arr, l, m);
sort(arr , m+1, r);
// Merging the sorted halves...
merge(arr, l, m, r);
}
}
// Merges two subarrays (halves) of arr[].
// First subarray is arr[l] <--> arr[m]
// Second subarray is arr[m+1] <--> arr[r]
void merge(int arr[], int l, int m, int r)
{
// Find sizes of two subarrays so that
// we can create temporary arrays of same size
// and for while condition
int n1 = m - l + 1; // + 1 as size should be 1 for single element where m = l = 0
int n2 = r - m;
/* Create temp arrays */
int leftTempArr[] = new int [n1];
int rightTempArr[] = new int [n2];
/*Copy data to temp arrays*/
for (int i=0; i<n1; i++)
leftTempArr[i] = arr[l + i]; // lowest index + i
for (int j=0; j<n2; j++)
rightTempArr[j] = arr[m + 1+ j]; // (mid+1) + j
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarry array
// Put number whichever is lower in arr[k]
int k = l;
while (i < n1 && j < n2)
{
if (leftTempArr[i] <= rightTempArr[j])
{
arr[k] = leftTempArr[i];
i++;
}
else
{
arr[k] = rightTempArr[j];
j++;
}
k++;
}
/* Copy remaining elements of leftTempArr[] if any */
while (i < n1)
{
arr[k] = leftTempArr[i];
i++;
k++;
}
/* Copy remaining elements of rightTempArr[] if any */
while (j < n2)
{
arr[k] = rightTempArr[j];
j++;
k++;
}
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String args[])
{
int arr[] = {11, 10, 12, 4, 5, 6};
System.out.println("Unsorted:");
printArray(arr);
MergeSortInJava ob = new MergeSortInJava();
ob.sort(arr, 0, arr.length-1);
System.out.println("\nSorted:");
printArray(arr);
}
}
/*
OUTPUT:
Unsorted:
11 10 12 4 5 6
Sorted:
4 5 6 10 11 12
*/
MergeSort Analysis
public class MergeSortAnalysis
{
void sort(int arr[], int l, int r)
{
if (l < r)
{
// Find mid
int m = (l+r)/2;
System.out.println("`````````````````````");
System.out.println("l: " + l + " | m: " + m + " | r: " + r);
System.out.println("`````````````````````");
// Sort first and second halves with recursion
sort(arr, l, m);
sort(arr , m+1, r);
// Merging the sorted halves...
merge(arr, l, m, r);
}
}
// Merges two subarrays (halves) of arr[].
// First subarray is arr[l] <--> arr[m]
// Second subarray is arr[m+1] <--> arr[r]
void merge(int arr[], int l, int m, int r)
{
// Find sizes of two subarrays so that
// we can create temporary arrays of same size
// and for while condition
int n1 = m - l + 1; // + 1 as size should be 1 for single element where m = l = 0
int n2 = r - m;
/* Create temp arrays */
int leftTempArr[] = new int [n1];
int rightTempArr[] = new int [n2];
/*Copy data to temp arrays*/
for (int i=0; i<n1; i++)
leftTempArr[i] = arr[l + i]; // lowest index + i
for (int j=0; j<n2; j++)
rightTempArr[j] = arr[m + 1+ j]; // (mid+1) + j
System.out.println("--------------------");
System.out.println("LEFT HALF");
printArray(leftTempArr);
System.out.println("--------------------");
System.out.println("--------------------");
System.out.println("RIGHT HALF");
printArray(rightTempArr);
System.out.println("--------------------");
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarry array
// Put number whichever is lower in arr[k]
int k = l;
while (i < n1 && j < n2)
{
if (leftTempArr[i] <= rightTempArr[j])
{
arr[k] = leftTempArr[i];
i++;
}
else
{
arr[k] = rightTempArr[j];
j++;
}
k++;
}
/* Copy remaining elements of leftTempArr[] if any */
while (i < n1)
{
arr[k] = leftTempArr[i];
i++;
k++;
}
/* Copy remaining elements of rightTempArr[] if any */
while (j < n2)
{
arr[k] = rightTempArr[j];
j++;
k++;
}
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String args[])
{
int arr[] = {11, 10, 12, 4, 5, 6};
System.out.println("****************");
System.out.println("Unsorted:");
printArray(arr);
System.out.println("****************");
MergeSortAnalysis ob = new MergeSortAnalysis();
ob.sort(arr, 0, arr.length-1);
System.out.println("****************");
System.out.println("Sorted:");
printArray(arr);
System.out.println("****************");
}
}
/*
OUTPUT:
****************
Unsorted:
11 10 12 4 5 6
****************
`````````````````````
l: 0 | m: 2 | r: 5
`````````````````````
`````````````````````
l: 0 | m: 1 | r: 2
`````````````````````
`````````````````````
l: 0 | m: 0 | r: 1
`````````````````````
--------------------
LEFT HALF
11
--------------------
--------------------
RIGHT HALF
10
--------------------
--------------------
LEFT HALF
10 11
--------------------
--------------------
RIGHT HALF
12
--------------------
`````````````````````
l: 3 | m: 4 | r: 5
`````````````````````
`````````````````````
l: 3 | m: 3 | r: 4
`````````````````````
--------------------
LEFT HALF
4
--------------------
--------------------
RIGHT HALF
5
--------------------
--------------------
LEFT HALF
4 5
--------------------
--------------------
RIGHT HALF
6
--------------------
--------------------
LEFT HALF
10 11 12
--------------------
--------------------
RIGHT HALF
4 5 6
--------------------
****************
Sorted:
4 5 6 10 11 12
****************
*/
Pratik Kataria is currently learning Springboot and Hibernate.
Technologies known and worked on: C/C++, Java, Python, JavaScript, HTML, CSS, WordPress, Angular, Ionic, MongoDB, SQL and Android.
Softwares known and worked on: Adobe Photoshop, Adobe Illustrator and Adobe After Effects.