Merge Sort 구현

C++를 이용하여 Merge Sort를 구현한 소스코드이다.

Merge를 할 때 원래는 마지막인지 체크를 하고 값을 넣는 과정이 있어야 하지만, 이렇게 하면 코드가 복잡해지기 때문에 합치려는 배열의 사이즈를 1씩 증가시켜서 마지막에 INT형 범위의 최댓값을 넣는 방법으로 구현하였다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

#include <iostream>   using namespace std;   #define INTMAX 2147483647   void mergeSort(int[], int, int); void merge(int[], int, int, int);   int main(){     int *arr, N;     cin >> N;     arr = new int[N];     for (int i = 0; i < N; i++)         cin >> arr[i];     mergeSort(arr, 0, N - 1);     for (int i = 0; i < N; i++)         cout << arr[i] << " ";     return 0; }   void mergeSort(int arr[], int s, int e){     if (s >= e){         return;     }     if (s + 1 == e){         if (arr[s] > arr[e]){             int tmp = arr[s];             arr[s] = arr[e];             arr[e] = tmp;         }     }     else {         int mid = (s + e) / 2;         mergeSort(arr, s, mid);         mergeSort(arr, mid + 1, e);         merge(arr, s, mid, e);     } }   void merge(int arr[], int s, int mid, int e){     int *t1 = new int[mid - s + 2];     int *t2 = new int[e - mid + 1];     for (int i = s; i <= mid; i++){         t1[i - s] = arr[i];     }     t1[mid - s + 1] = INTMAX;     for (int i = mid + 1; i <= e; i++){         t2[i - mid - 1] = arr[i];     }     t2[e - mid] = INTMAX;     int j = 0, k = 0;     for (int i = s; i <= e; i++){         if (t1[j] < t2[k]){             arr[i] = t1[j++];         }         else {             arr[i] = t2[k++];         }     }     delete[] t1;     delete[] t2; }

메인함수 부분에서는 N개의 데이터를 입력 받아서 그 데이터를 MergeSort를 이용해서 정렬하고, 결과를 출력한다.