Home > Java, Java Misc, Java Sorting > Merge Sort in Java

Merge Sort in Java

Here it is:

package com.labeltop.sort;

public class MergeSort {

	public void sort(Comparable[] c) {
		mergesort(c, 0, c.length-1);
	}

	private void mergesort(Comparable[] c, int start, int end) {
		//check if sort is needed
		if (c.length <= 1)
			return;
		
		//find middle
		int middle = start + ((end-start)/2);
		
		//create left list
		Comparable[] cLeft = new Comparable[middle-start+1];
		
		//create right list
		Comparable[] cRight = new Comparable[end-middle];
		
		//sort first half
		mergesort(cLeft, 0, cLeft.length-1);
		//sort second half
		mergesort(cRight, 0, cRight.length-1);
		
		//check the last on left iwth first on right to see if we need to merge
		if (cLeft[cLeft.length-1].compareTo(cRight[0]) <= 0) {
			System.arraycopy(cLeft, 0, c, 0, cLeft.length);
			System.arraycopy(cRight, 0, c, cLeft.length, cRight.length);
		}
		else {
			//now merge left and right
			mergeIt(c, cLeft, cRight);	
		}
	}
	
	private void mergeIt(Comparable[] merged, Comparable[] cLeft, Comparable[] cRight) {		
		//loop till both are done
		int iMerged = 0;
		int iLeft = 0;
		int iRight = 0;
		while (iLeft < cLeft.length && iRight < cRight.length)
		{
			if (cLeft[iLeft].compareTo(cRight[iRight]) <= 0)
			{
				//copy from left
				merged[iMerged] = cLeft[iLeft];
				iLeft++;				
			}
			else
			{
				//copy from right
				merged[iMerged] = cRight[iRight];
				iRight++;
			}
			
			iMerged++;
		}
		
		//check for remaining elements on left
		if (iLeft <= cLeft.length-1) {
			System.arraycopy(cLeft, iLeft, merged, iMerged, cLeft.length-iLeft);
			iMerged = iMerged + (cLeft.length-1-iLeft);
		}
		//check for remaining elements on right
		if (iRight <= cRight.length-1) {
			System.arraycopy(cRight, iRight, merged, iMerged, cRight.length-iRight);
			iMerged = iMerged + (cRight.length-1-iRight);
		}		
	}
}
Advertisements
Categories: Java, Java Misc, Java Sorting
  1. No comments yet.
  1. No trackbacks yet.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: