Merge Sort Algorithm

A basic implementation of a merge sort algorithm.

Running a test file of 100000 randomly ordered integers through this algorithm takes about 4.54 seconds on my system. I will be using the same test file for comparison against other sorting algorithms.

Josh


/**
 * A very basic Merge Sort class implemented from a pseudocode 
 * algorithm found on Wikipedia
 * 
 * This class will only sort an int[].
 * 
 * @author Joshua Weise
 * @see http://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation
 */
public class MergeSort {

	// array of numbers
	private int[] data;
	
	public MergeSort(int[] data) {
		this.data = data;	
	}
	
	/**
	 * starts the recursive mergeSort method
	 */
	public void sort() {	
		data = mergeSort(data);			
	}
	
	
	/**
	 * Recursively splits the initial data array and calls
	 * the merge method to sort and recombine the data
	 * @param m		numbers to sort
	 * @return		new sorted array
	 */
	private int[] mergeSort(int[] m) {
		
		if (m.length <= 1) { return m; }
		
		int[] left = new int[m.length / 2];
		int[] right = new int[m.length - left.length];
		int middle = m.length / 2;
		
		for (int i = 0; i < middle; i++) {
			left[i] = m[i];
		}
		
		for (int i = 0; i < right.length; i++) {
			right[i] = m[i + left.length];
		}
		
		left = mergeSort(left);
		right = mergeSort(right);
		
		return merge(left, right);
	}
	
	
	/**
	 * Merges two number arrays while also putting them in order
	 * @param left		numbers to sort and merge
	 * @param right		numbers to sort and merge
	 * @return			new sorted and merged array
	 */
	private int[] merge(int[] left, int[] right) {
		int[] result = new int[left.length + right.length];
		int x = 0;
		
		while (left.length > 0 || right.length > 0) {
			if (left.length > 0 && right.length > 0) {
				if (left[0] <= right[0]) {
					result[x] = left[0];
					x++;
					left = shiftLeft(left);
				} else {
					result[x] = right[0];
					x++;
					right = shiftLeft(right);
				}
			} else if (left.length > 0) {
				result[x] = left[0];
				x++;
				left = shiftLeft(left);
			} else if (right.length > 0) {
				result[x] = right[0];
				x++;
				right = shiftLeft(right);
			}
		}		
		return result;
	}

	
	/**
	 * removes the leftmost array item by returning a new array
	 * with everything but that item
	 * @param x		array of numbers
	 * @return		new array of numbers
	 */
	private int[] shiftLeft(int[] x) {
		int[] y = new int[x.length - 1];
		for (int i = 1; i < x.length; i++) {
			y[i-1] = x[i];
		}		
		return y;
	}
	
	
	// return data
	public int[] getData() {
		return data;
	}
	
}

This entry was posted in Java, Sorting Algorithms. Bookmark the permalink.

Leave a Reply