From DojoWiki

September 27th Meeting

Topic Sorting

I worked up part of a MergeSort.. Here is the Java code.

package org.pghcodingdojo.sorting ;


public class Sorter {
    private static int[] unsortedArray = new int[] {38, 27, 43, 3, 9, 82, 10} ;
    public static void main(String[] args) {

		int[] sortedList = mergeSort(unsortedArray) ;
		for (int i : sortedList) System.out.println("" + i) ; 
	}

    private static int[] mergeSort(int[] unsortedArray) {
        int middle = unsortedArray.length / 2;
        int[] left = new int[middle];
        int[] right = new int[unsortedArray.length - middle];
        
        int[] result = new int[unsortedArray.length];
        if (unsortedArray.length <= 1) {
            return unsortedArray;
        } else {

            for (int i = 0; i < middle; i++) {
                left[i] = unsortedArray[i];
            }
            
            for (int j = 0, i = middle; i < unsortedArray.length; i++, j++) {
            	int insert = unsortedArray[i];
            	System.out.printf("unsortedArray length is %x Array Length is %x and index is %x\n", 
            			unsortedArray.length, right.length, j) ; 
            	right[j] = insert ; 
            }
            left = mergeSort(left);
            right = mergeSort(right);
            result = merge(left, right) ;
            return result;

        }

    }

    private static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int resultAppendIdx = 0 ; 
        int leftCounter = left.length ;
        int rightCounter = right.length ;
        while (leftCounter > 0 && rightCounter > 0) {
        	if (left[0] <= right[0]) {
        		result[resultAppendIdx++] = left[0] ; 
        		
        		int[] temp = new int[left.length-1] ; 
        		for (int i = 1; i<left.length; i++) {
        			temp[i-1] = left[i] ;  
        		}
        		left = temp ; 
        		
        	}
        	else {
        		result[resultAppendIdx++] = right[0] ;
//shift array values, and drop the first index...
        		int[] temp = new int[right.length-1] ; 
        		for (int i = 1; i<right.length; i++) {
        			temp[i-1] = right[i] ;  
        		}
        		right = temp ; 
        	}
        	leftCounter = left.length ; 
        	rightCounter = right.length ;
        	
        }
        if (left.length > 0) {
    		for (int i : left) result[resultAppendIdx++] = i ; 
    	}
    	if (right.length > 0) {
    		for (int i : right) result[resultAppendIdx++] = i ; 
    		
    	}
        

        return result ; 
    }

}