How to implement merge Sort and complexity O(nlogn)

How to implement merge Sort and complexity will be O(nlogn)

SOURCE : MyMergeSort.java

public class MyMergeSort {
	private int[] array;
	private int[] tempMergArr;
	private int length;

	public static void main(String a[]) {

		int[] inputArr = { 45, 23, 11, 89, 77, 98, 4, 28, 65, 43 };
		MyMergeSort mms = new MyMergeSort();
		mms.sort(inputArr);
		for (int i : inputArr) {
			System.out.print(i);
			System.out.print(" ");
		}
	}

	public void sort(int inputArr[]) {
		this.array = inputArr;
		this.length = inputArr.length;
		this.tempMergArr = new int[length];
		doMergeSort(0, length - 1);
	}

	private void doMergeSort(int lowerIndex, int higherIndex) {

		if (lowerIndex < higherIndex) {
			int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
			// Below step sorts the left side of the array
			doMergeSort(lowerIndex, middle);
			// Below step sorts the right side of the array
			doMergeSort(middle + 1, higherIndex);
			// Now merge both sides
			mergeParts(lowerIndex, middle, 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;

		// merging two arrays
		while (i <= middle && j <= higherIndex) {

			if (tempMergArr[i] <= tempMergArr[j]) {
				array[k++] = tempMergArr[i++];

			} else {
				array[k++] = tempMergArr[j++];

			}

		}
		while (i <= middle) {
			array[k++] = tempMergArr[i++];

		}

	}

}

INPUT

{ 45, 23, 11, 89, 77, 98, 4, 28, 65, 43 }

OUTPUT

 4 11 23 28 43 45 65 77 89 98 

Hi, I have written and developed this post so that most of people will be benefited. I'm committed to provide easy and in-depth tutorials on various technologies.I hope it will help you a lot.
- Sandeep Kumar D

Follow Me @Google+

SHARE

Onlinecodegeek