Running time - O(n log n)
Java Implementation with primitive array
public class MergeSort {
/**
* @param args
*/
public static void main(String[] args) {
int[] input = new int[]{8,7,6,5,4,3,2,1,10};
System.out.println(" INPUT :: "+ input);
int[] output = splitMerge(input,0,input.length);
for(int x=0;x < output.length;x++){
System.out.print(" OUTPUT :: "+ output[x] + " ");
}
}
public static int[] splitMerge(int[] data, int start, int length){
if(length > 1) {
int l = length/2;
int l1 = length - l;
splitMerge(data, start, l);
splitMerge(data, start + l, l1);
merge(data, start, l, l1);
}
return data;
}
private static void merge(int[] data, int start, int l, int l1 ){
int[] temp = new int[l+l1];;
int i = 0;
int j = 0 ;
int k = 0;
while(i < l && j < l1){
if(data[start + i] <= data[start + l + j]){
temp[k] = data[start + i];
i++;
}
else if(data[start + l + j] < data[start + i]){
temp[k] = data[start + l + j];
j++;
}
k++;
}
while(j < l1){
temp[k] = data[start + l + j];
j++;
k++;
}
while(i < l){
temp[k] = data[start + i];
i++;
k++;
}
for(int m=0;m < temp.length;m++){
data[start + m] = temp[m];
}
System.out.println();
}
}
Java Implementation with primitive array
public class MergeSort {
/**
* @param args
*/
public static void main(String[] args) {
int[] input = new int[]{8,7,6,5,4,3,2,1,10};
System.out.println(" INPUT :: "+ input);
int[] output = splitMerge(input,0,input.length);
for(int x=0;x < output.length;x++){
System.out.print(" OUTPUT :: "+ output[x] + " ");
}
}
public static int[] splitMerge(int[] data, int start, int length){
if(length > 1) {
int l = length/2;
int l1 = length - l;
splitMerge(data, start, l);
splitMerge(data, start + l, l1);
merge(data, start, l, l1);
}
return data;
}
private static void merge(int[] data, int start, int l, int l1 ){
int[] temp = new int[l+l1];;
int i = 0;
int j = 0 ;
int k = 0;
while(i < l && j < l1){
if(data[start + i] <= data[start + l + j]){
temp[k] = data[start + i];
i++;
}
else if(data[start + l + j] < data[start + i]){
temp[k] = data[start + l + j];
j++;
}
k++;
}
while(j < l1){
temp[k] = data[start + l + j];
j++;
k++;
}
while(i < l){
temp[k] = data[start + i];
i++;
k++;
}
for(int m=0;m < temp.length;m++){
data[start + m] = temp[m];
}
System.out.println();
}
}
No comments:
Post a Comment