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
Post a Comment