Merge sort (병합정렬, 합병정렬, 머지소트)

알고리즘
1. 정렬되지 않은 리스트들을 원소가 1개인 하위리스트들로 나눔.
2. 분할된 하위리스트들을 합병하면서 새로운 하위리스트들을 만들고, 최종적으로 1개의 리스트로 합병함.

시간복잡도
최악 : O(n log n)
최선 : O(n log n)
평균 : O(n log n)

소스

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

public class MergeSort {
     /**
     * @param args
     */
     public static void main(String[] args) {
          
          int nData = 16;     //정렬할 데이터 개수 설정.
          double TargetDataList[] = new double[nData]; 
          
          //데이터 생성
          for(int i = 0; i < nData; i++)
          {
               TargetDataList[i] = Math.random();
               
               System.out.print(TargetDataList[i]+" ");     //데이터 출력
          }
          System.out.println();

          // 분할
          List splitedData = new ArrayList();
          for (int i = 0; i < TargetDataList.length; i++) {
               double[] tmpData = new double[1];
               tmpData[0] = TargetDataList[i];
               splitedData.add(tmpData);
          }

          // 합병
          List sortedData = merge(splitedData);
          
          while(sortedData.size() > 1){
               sortedData = merge(sortedData);
          }

          //정렬된 데이터 확인.
          for(int i =0; i < sortedData.size(); i++){
               double[] result = (double[])sortedData.get(i);
               for(int k = 0; k < result.length; k++){
                    System.out.print(result[k] + " ");
               }
          }
          System.out.println();
          
     }
     
          


     private static List merge(List splitedData) {

          List mergedData = new ArrayList();
          
          for(int i = 0; i < splitedData.size(); i=i+2){
               double[] leftData = (double[])splitedData.get(i);
               double[] rightData = (double[])splitedData.get(i+1);
               
               
               int nMergedLeft = 0;
               int nMergedRight = 0;
               double[] partialMergedData = new double[leftData.length + rightData.length];
               for(int partialIdx = 0; partialIdx < partialMergedData.length; partialIdx++){
                    
                    if(leftData.length <= nMergedLeft){
                         partialMergedData[partialIdx] = rightData[nMergedRight];
                         nMergedRight++;
                    }else if(rightData.length <= nMergedRight){
                         partialMergedData[partialIdx] = leftData[nMergedLeft];
                         nMergedLeft++;
                    }else if(leftData[nMergedLeft] <= rightData[nMergedRight]){
                         partialMergedData[partialIdx] = leftData[nMergedLeft];
                         nMergedLeft++;
                    }else{
                         partialMergedData[partialIdx] = rightData[nMergedRight];
                         nMergedRight++;
                    }
               }
               
               mergedData.add(partialMergedData);
          }
          
          return mergedData;
     }
}

참고
1. http://en.wikipedia.org/wiki/Merge_sort