Merge sort | Recursive Java program | Improvement | Use Insertion sort for small sub array


class MergeSort {
    // use CUTOFF to sort small sub array
    // CUTOFF can be taken 7 to 10 items
    private static final int CUTOFF = 4;
    
    public static void sort(int[] array) {
        // auxilary array of size O(n) used by merge process
        int[] aux = new int[array.length];
        sort(array, aux, 0, array.length-1);
    }
    
    private static void sort(int[] array, int[] aux, int low, int high) {
        // Improvement 1 ::
        // Using insertion sort for small sub array 
        // For first pass skip the InsertionSort
        if(high <= low + CUTOFF - 1) {
            InsertionSort.sort(array, low, high);
            return; // sorting not required
        }
        int mid = low + (high-low)/2;
        sort(array, aux, low, mid);
        sort(array, aux, mid+1, high);
        merge(array, aux, low, mid, high);
    }
    
    private static void merge(int[] array, int[] aux, int low, int mid, int high) {
        // copy from array to aux 
        int i = low;
        for(; i <= high; i++) {
            aux[i] = array[i];
        }
        
        // merge aux to array 
        i = low; // used for first sub array 
        int j = mid+1; // used for second sub array 
        int k = low; // used for merged array 
        while(k <= high) {
            if(i > mid) {
                array[k++] = aux[j++];
            } else if(j > high) {
                array[k++] = aux[i++];
            } else if(less(aux[i], aux[j])) {
                array[k++] = aux[i++];
            } else {
                array[k++] = aux[j++];
            }
        }
    }
    
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    
    private static boolean less(int key1, int key2) {
        return key1 < key2;
    }
    
    private static void display(int[] array) {
        for(int key : array) {
            System.out.print(key + " ");
        }
    }
    
	public static void main (String[] args) {
		int[] array = new int[] {11,13,7,12,16,9,24,15,2,4,6,0,20,22,5,10,3};
		System.out.println("Unsorted array : ");
		display(array);
		
		sort(array);
		System.out.println("\nSorted array : ");
		display(array);
	}
	
	private static class InsertionSort {
	    static void sort(int[] array, int low, int high) {
	        for(int i = 1; i <= high; i++) {
	            for(int j = i; j > 0; j--) {
	                if(less(array[j], array[j-1])) {
	                    swap(array, j, j-1);
	                }
	            }
	        }
	    }
	}
}

Unsorted array : 
11 13 7 12 16 9 24 15 2 4 6 0 20 22 5 10 3 
Sorted array : 
0 2 3 4 5 6 7 9 10 11 12 13 15 16 20 22 24 

Comments

Popular posts from this blog

SQL basic interview question

gsutil Vs Storage Transfer Service Vs Transfer Appliance