[java] Merge Sort(합병정렬)

안녕하세요 요번에는 삽입정렬에 대해서 공부했습니다 

 

삽입정렬이란 input array 를 반으로 나누고 또 다시 반으로 나누고 더 이상 나눌 수 없을 정도로 나누고 나서 합처서 

 

결과를 얻는 방식입니다 앞서 작성했던 Insertion Sort 는 Incremental approach(점진적 접근방식) 이라고 하면

 

merge sort 는 Divide and Conquer approach 입니다 

 

알고리즘 에 있어서  Divide and Conquer approach 는 정말 중요한 방식이므로 숙지 할 필요가 있습니다!!

 

분할 정복 알고리즘(Divide and conquer algorithm)이란 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법입니다

앞으로 알고리즘을 공부하거나 코딩테스트를 준비하는 학생, 취준생 등등 여러 분들은 이 개념을 꼭 숙지하시기 바랍니다!! 

 

자 그럼 Merge Sort 의 시간은 어떻게 계산 될까요??

Merge Sort 의 걸리는 시간이 T(n) 이라고 한다면

T(n) = T(Divide) + T(Conquer)+ T(Combine) 입니다  

 

Merge Sort 의 시간 복잡도는 O(nlogn) 이 나오게 됩니다

 

 

앞서 공부 했던 Insertion Sort 보다 훨씬 효율적인 시간 복잡도를 확인 할 수 있다 즉 worst case 인 경우 Merge Sort 가 훨씬 빠르다는 걸 알 수 있다 그러나 Best case 인경우 Merge Sort는 Best case 인 경우에도 O(nlogn) 이지만 Insertion Sort 는 O(n) 으로 이때는 Insertion Sort 가 더 빠르 다는 걸 알 수 있다 그러나 우리 자연 세계에서는 best case 인 경우(이미 정렬된 List) 는 극히 적으므로 만약 정렬시스템을 구축하게 될 경우 Insertion sort 보다 Merge Sort 나 나중에 공부 할 Quick Sort 등등 으로 시스템을 구축 하는것이 훨씬 효율적이다!!

 

Merge Sort 알고리즘 은 어떤 식으로 정렬 해 나갈까요?? 밑에 이미지를 보면 쉽게 이해 하 실 수 있습니다!~

 

 

자바 코드로 구현 하면 이런식으로 구현 할 수 있습니다!!