搜尋此網誌

2012年3月25日 星期日

Merge Sort (合併排序法)


package sort;

public class MergeSortDemo {


public static void main(String[] args) {
int[] array = { 3, 3,2,1,0,4,5,1,4};
array = mergeSort(array);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}

public static int[] mergeSort(int[] list) {
//if merely left 1 element return list;
if (list.length <= 1) {
return list;
} else {
int[] left;
int[] right;
int middle = list.length / 2;
//declare left sub array;
left = new int[middle];
//declare right sub array;
right = new int[list.length - middle];
int j = 0;
for (int i = 0; i < list.length; i++) {
if (i < left.length) {
//initialize left array
left[i] = list[i];
} else {
//initialize right array
right[j] = list[i];
j++;
}
}
//divide left array into small parts;
left = mergeSort(left);
//divide right array into small parts;
right = mergeSort(right);
//combine small parts of left and right
return merge(left, right);
}
}

public static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int j = 0;
while (left.length > 0 || right.length > 0) {
//left and right array have elements.
if (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result[j] = left[0];
left = shiftArray(left);
} else {
result[j] = right[0];
right = shiftArray(right);
}

} else if (left.length > 0) {
//left array has elements;
result[j] = left[0];
left = shiftArray(left);
} else if (right.length > 0) {
//right array has elements;
result[j] = right[0];
right = shiftArray(right);
}
j++;
}
return result;
}

private static int[] shiftArray(int[] i) {
int[] result = new int[i.length - 1];
for (int j = 0; j < result.length; j++) {
result[j] = i[j+1];
}
return result;
}
}




Reference Wiki