Merge Sort Java Implementation

Algorithms 
import java.util.Arrays;

public class MergeSort {
	public static void sort(int[] inputArray) {
		sort(inputArray, 0, inputArray.length-1);
	}
	
	public static void sort(int[] inputArray, int start, int end) {
		if(end <=start) {
			return; // array travels seems done
		}
		
		int mid = (start + end) / 2;
		sort(inputArray, start, mid);
		sort(inputArray, mid+1,end);
		merge(inputArray, start, mid, end);
	}
	
	public static void merge(int[] inputArray, int start, int mid, int end) {
		int tempArray[] = new int[end - start+1];
		int leftCounter = start;
		int rightCounter = mid+1;
		
		int tempArrayCounter=0;
		while(leftCounter <=mid && rightCounter<=end) {
			if(inputArray[leftCounter] < inputArray[rightCounter]) {
				tempArray[tempArrayCounter]=inputArray[leftCounter];
				leftCounter++;
			}else {
				tempArray[tempArrayCounter]=inputArray[rightCounter];
				rightCounter++;
			}
			tempArrayCounter++;
		}
		
		// left and right should have been sorted by now
		if(leftCounter <= mid) {
			while(leftCounter <= mid) {
				tempArray[tempArrayCounter] = inputArray[leftCounter];
				leftCounter++;
				tempArrayCounter++;
			}
		} else if(rightCounter <= end) {
			while(rightCounter <= end) {
				tempArray[tempArrayCounter]= inputArray[rightCounter];
				rightCounter++;
				tempArrayCounter++;
			}
		}
		
		// copy temp array to input array
		for(int i =0;i<tempArray.length;i++) {
			inputArray[start+i] = tempArray[i];
		}
		
	}
	
	public static void main(String[] args) {
		int[] inputArray = {9,7,3,10,1,8,4,6};
		sort(inputArray);
		System.out.println(Arrays.toString(inputArray));
	}
}

Output:

[1, 3, 4, 6, 7, 8, 9, 10]
11 comments

11 comments

Leave a Reply