하도 손디버깅을 많이해서 그런가 코드를 그냥 외워버려서 쭉 치긴 했는데 사실 블로그 배껴서 작성한겁니다 ㅠㅠ
아직도 잘 이해가 안가는 코드입니다.(재귀함수 연상이 어렵네요... 그래서 재귀를 안쓰고 구현해보려고 했는데 실패했습니다 ㅠㅠㅠ)
거기다 이유는 모르겠지만 제가 작성한 삽입정렬보다 느립니다. 원래 빨라야 할것 같은데....
머릿속으로 그려낸걸 코드로 옮기기란 정말 어렵습니다.
public int[] mergeSort(int[] array) {
long startTime = System.nanoTime();
array = Merge_Sort(array, 0, array.length - 1);
long endTime = System.nanoTime();
System.out.println("MergeSort TIME : " + (endTime - startTime) / 1000.0 + "(ms)");
return array;
}
private int[] Merge_Sort(int[] array, int start, int end) {
if(start < end) {
int middle = (start + end)/2;
Merge_Sort(array, start, middle);
Merge_Sort(array, middle + 1, end);
merge(array, start, middle, end);
}
return array;
}
private void merge(int[] array, int start, int middle, int end) {
int leftIndex = start;
int rightIndex = middle+1;
int tempIndex = start;
int temp[] = new int[array.length];
while(leftIndex <= middle && rightIndex <= end) {
if(array[leftIndex] < array[rightIndex]) {
temp[tempIndex++] = array[leftIndex++];
}else {
temp[tempIndex++] = array[rightIndex++];
}
}
while(leftIndex <= middle)
temp[tempIndex++] = array[leftIndex++];
while(rightIndex <= end)
temp[tempIndex++] = array[rightIndex++];
for(int index = start; index < tempIndex; index++)
array[index] = temp[index];
}
<<100개 데이터 정렬 결과(시간)>>
InsertionSort TIME : 56.19(ms)
MergeSort TIME : 65.555(ms)
삽입정렬보다 엄청 느리네요...
글쓰기