归并排序的java实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
* 归并排序的java实现
*
* @version 1.0 2011-07-13 10:10
* @author 鬼辅神攻
*
*/
public class MergeSort {
/**
* @param <T>
*            必须实现了Comparable接口
* @param list
*            待排序数组
* @return 正序排列的结果
*/
public static <T extends Comparable<T>> List<T> sort(List<T> list) {
int size = list.size();
// 结束条件，数组长度为1
if (size < 2) {
return list;
}
return merge(sort(list.subList(0, size / 2)), sort(list.subList(
size / 2, size)));
}

/**
* 采用正序排列
*
* @param <T>
* @param leftArray
*            必须是已经排过序的
* @param rightArray
*            必须是已经排过序的
* @return 排过序的数组
*/
private static <T extends Comparable<T>> List<T> merge(List<T> leftArray,
List<T> rightArray) {
List<T> result = new ArrayList<T>();

int j = 0;// right array index

for (int i = 0; i < leftArray.size(); i++) {
T left = leftArray.get(i);
// compare to the next of right array, till >=
for (; j < rightArray.size();) {
T right = rightArray.get(j);
if (left.compareTo(right) <= 0) {
result.add(left);
break;
} else {
// add the next of right array to result
result.add(right);
j++;
continue;
}
}
// if the leave of the left array is exist, add all to the result.
if (j >= rightArray.size()) {
result.add(left);
continue;
}
}
// if the leave of the right array is exist, add all to the result.
for (; j < rightArray.size(); j++) {
result.add(rightArray.get(j));
}
return result;
}

// test
public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>(Arrays
.asList(new Integer[] { 3, 4, 3, 73, 23, 11, 34 }));
System.out.println("result:");
System.out.println(MergeSort.sort(list).toString());
}
}