MergeSort

분할정복으로 행열을 쪼갤만큼 쪼갠다음 merge하면서 sort한다 항상 nlogn 하지만 일반적으로 quick sort가 빠름

출처 : http://yujuwon.tistory.com/entry/%EB%B3%91%ED%95%A9%EC%A0%95%EB%A0%ACMerge-Sort

예제 파일 : https://gist.github.com/yujuwon/5810996#file-gistfile1-c

import java.util.Arrays;

public class MeargeSort20160305 {

public static void main(String args[]) {

int[] arr = { 1, 3, 3, 4, 5, 2, 7 };

int[] temp = new int[arr.length];

mergeSort(arr, temp, 0, arr.length - 1);

System.out.println(Arrays.toString(arr));

}

public static void mergeSort(int[] arr, int[] temp, int l, int r) {

if (l < r) {

int mid = l + (r - l) / 2;

mergeSort(arr, temp, l, mid);

mergeSort(arr, temp, mid + 1, r);

   // Copy both parts into the helper array

   for (int i = l; i <= r; i++) {

     temp[i] = arr[i];

   }

   int i = l;

   int j = mid + 1;

   int k = l;

   // Copy the smallest values from either the left or the right side back

   // to the original array

   while (i <= mid && j <= r) {

     if (temp[i] <= temp[j]) {

       arr[k] = temp[i];

       i++;

     } else {

       arr[k] = temp[j];

       j++;

     }

     k++;

   }

   // Copy the rest of the left side of the array into the target array

   while (i <= mid) {

     arr[k] = temp[i];

     k++;

     i++;

   }

}

}

}