WOOHU

정렬 정리

병합정렬은 N개의 원소에 대해 N/2개로 분리하고 또 N/4개 .....  N/(2^N)개로 나눈후 합치면서 정렬해나가는 정렬방법이다.

분할하는 과정은 재귀함수를 통하여 분할을한다.

원소가 1개 까지 남는 과정을 재귀를 통하여 분할하도록하는데

이때 if문을 통하여 확인한다  //if(left<right)

분할이 완료되었다면 병합하는 함수를 호출해준다. //marge_sort(arr, left, mid, right)

병합하는 과정은 다음과같은데 left ~ mid 부분의 원소와 mid+1 ~ right 부분의 원소를 크기순으로 구분하고

병합해주도록 한다.

이떄 한쪽의 원소가 모두 정렬이 된다면 남은 한쪽의 원소를 전부 넣어준다(한쪽원소들보다 클수밖에 없으므로)

이과정을 재귀를 통해 모두수행하고나면 정렬이 완료된다.

10만개의 배열을 랜덤하게 생성후 정렬한 결과.