Merge Sort Example in Java


package in.malliktalksjava;

/**
* @author malliktalksjava
*
* Sorts the given array using merge sort algorithm
*/
public class MergeSortExample {

private int[] array;
private int[] tempMergArr;
private int length;

/**
* @param args
*
* main method.
* Pass the array to sort method and prints the output array into console.
*/
public static void main(String args[]){

int[] inputArr = {12,25,36,95,86,21,14,52,85,32};
MergeSortExample mergeSorter = new MergeSortExample();
mergeSorter.sort(inputArr);
for(int sortedValue:inputArr){
System.out.print(sortedValue);
System.out.print(” “);
}
}

/**
* @param inputArr
*
* Checks given array is null of not, then pass it to mergeSort Method.
*/
public void sort(int[] inputArr) {

if (inputArr == null || inputArr.length == 0) {
System.out.println(“Given Array is null or does not contain any elements”);
return;
}

this.array = inputArr;
this.length = inputArr.length;
this.tempMergArr = new int[length];
mergeSort(0, length – 1);
}

/**
* @param lowerIndex
* @param higherIndex
*
* Sorts the array using mergesort algorithm.
*/
private void mergeSort(int lowerIndex, int higherIndex) {

if (lowerIndex < higherIndex) {
int middle = lowerIndex + (higherIndex – lowerIndex) / 2;
// sort the left side of the array
mergeSort(lowerIndex, middle);
// sort the right side of the array
mergeSort(middle + 1, higherIndex);
// merge both sides
mergeParts(lowerIndex, middle, higherIndex);
}
}

/**
* @param lowerIndex
* @param middle
* @param higherIndex
*
*
*/
private void mergeParts(int lowerIndex, int middle, int higherIndex) {

for (int i = lowerIndex; i <= higherIndex; i++) {
tempMergArr[i] = array[i];
}
int i = lowerIndex;
int j = middle + 1;
int k = lowerIndex;
while (i <= middle && j <= higherIndex) {
if (tempMergArr[i] <= tempMergArr[j]) {
array[k] = tempMergArr[i];
i++;
} else {
array[k] = tempMergArr[j];
j++;
}
k++;
}
while (i <= middle) {
array[k] = tempMergArr[i];
k++;
i++;
}
}
}

 

Other Useful Links:

Quick Sort Example Program in Java

Insertion Sort Example program in JAVA

Selection Sort Example Program in Java

Bubble Sort Example in JAVA

4 thoughts on “Merge Sort Example in Java

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.