[알고리즘 9.2.1] 고급정렬 - 합병정렬 구현

문제

---

서로 다른 n개의 정수가 주어질 때, 이를 합병정렬을 이용하여 오름차순으로 정렬하는 프로그램을 작성하시오.

 

입력

---

첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 100,000 ) 두번째 줄에 n개의 정수가 주어진다.  

출력

---

첫 번째 줄에 n개의 숫자를 합병정렬을 이용하여 오름차순으로 정렬한 결과를 출력한다.

 

예제 입력

10 2 5 3 4 8 7 -1 9 10 2

예제 출력

-1 2 2 3 4 5 7 8 9 10

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#include <stdio.h>
 
void merging(int arr[], int s1, int e1, int s2, int e2);
void mergeSort(int arr[], int start, int end){
  
  if(start>=end){
    return;
  }else{
    
    int mid = (start+end)/2;
    
    mergeSort(arr, start, mid);
    mergeSort(arr, mid+1, end);
    
    merging(arr, start, mid, mid+1, end);
    
  }
  
}
 
void merging(int arr[], int s1, int e1, int s2, int e2){
  
  int p = s1;
  int q = s2;
  int temp[100005];
  int temp_idx=0;
  
  while(p<=e1 && q<= e2){
    
    if(arr[p]<=arr[q]){
      temp[temp_idx++] = arr[p];
      p++;
    }else{
      temp[temp_idx++] = arr[q];
      q++;
    }
    
  }
  
  if(p>e1){
    for(int i=q; i<=e2; i++){
      temp[temp_idx++] = arr[i];
    }
  }else{
    for(int i=p; i<=e1; i++){
      temp[temp_idx++] = arr[i];
    }
  }
  
  for(int i=s1; i<=e2; i++){
    arr[i] = temp[i-s1];
  }
  
}
 
int main() {
  
  int n;
  int numbers[100005];
  
  scanf("%d",&n);
  
  for(int i=0; i<n; i++) scanf("%d",&numbers[i]);
  
  mergeSort(numbers, 0, n-1);
  
  for(int i=0; i<n; i++) printf("%d ",numbers[i]);
  
  return 0;
}