병합 정렬 mergesort with swift

병합 정렬은 반으로 나누고 합치면서 정렬합니다.

 

코드를 살펴봅시다.

 

위 코드에서 mergeSort 함수는 반으로 나누는 역할을 하며 merge함수는 합치는 역할을 합니다.

 

큰 흐름을 살펴보면

 

 

mergeSort함수를 통해 중간 인덱스를 잡고 왼쪽 오른쪽으로 나눕니다.

나눈 배열을 재귀로 다시 mergeSort로 넘깁니다.

그리고 배열의 길이가 1이면 리턴하게 됩니다.

그럼 배열 count가 1이 될 때까지 나누어지겠죠.

 

이후 나뉜 배열에 대해서 merge가 실행됩니다. 

 

merge가 실행되는 순서는 위와 같습니다.

[1][5]에서 처음 merge가 실행되며

[4][1,5]에서 두 번째 merge가 실행되며

[3][6]에서 세 번째 merge가 실행되며

[2][7]에서 네 번째 merge가 실행되며

[3,6][2,7]에서 다섯 번째 merge가 실행되고

마지막으로 [1,4,5][2,3,6,7]에서 여섯 번째 merge가 실행됩니다.

 

merge함수를 통해 왼쪽 오른쪽 배열을 받고 비교하며 순서대로 ordered에 append 됩니다.

즉 merge함수를 통해 정렬된 배열을 리턴 받을 수 있습니다.

 

시간 복잡도는 O(nlogn)이며 이전에 나온 삽입, 선택, 버블 정렬보다는 훨씬 효율적인 정렬이라고 말할 수 있습니다.

이는 pivot값에 상관없이 나누고 합치기 때문에 항상 logn과 같은 시간 복잡도를 가집니다.