# 병합 정렬

### 수 정렬하기2&#x20;

#### Question - 2751

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2FhnUhAW8KFNXScrwAUl7j%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-06-08%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%2012.13.11.png?alt=media\&token=f1f381cf-7d4c-4b3b-831d-0dc9bdc4d24c)

#### Code

{% tabs %}
{% tab title="병합 정렬" %}
```java
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    
    public static int[] A, tmp;
    public static long result;
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        A = new int[N + 1];
        tmp = new int[N + 1];
    
        for (int i = 1; i <= N; i++) {
            A[i] = Integer.parseInt(br.readLine());
        }
    
        merge_sort(1 , N);
        for (int i = 1; i <= N; i++) {
            bw.write(A[i] + "\n");
        }
    
        bw.flush();
        bw.close();
    }
    
    private static void merge_sort(int s, int e) {
        if ( e - s < 1)
            return ;
        int m = s + (e - s) / 2;
        
        merge_sort(s, m);
        merge_sort(m + 1, e);
        
        for (int i = s; i <= e; i++) {
            tmp[i] = A[i];
        }
        
        int k = s;
        int index1 = s;
        int index2 = m + 1;
        while (index1 <= m && index2 <= e) {
            if (tmp[index1] > tmp[index2]) {
                A[k] = tmp[index2];
                k++;
                index2++;
            } else {
                A[k] = tmp[index1];
                k++;
                index1++;
            }
        }
        while (index1 <= m) {
            A[k] = tmp[index1];
            k++;
            index1++;
        }
        while (index2 <= e) {
            A[k] = tmp[index2];
            k++;
            index2++;
        }
    }
}
```


{% endtab %}

{% tab title="함수" %}
```java
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class N20_P2751_수_정렬하기2 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(A);

        for (int i = 0; i < N; i++) {
            bw.write(A[i] + "\n");
        }
        bw.flush();
        bw.close();
    }
}

```
{% endtab %}
{% endtabs %}

#### Isight

#### Idea

#### reference



### 버블 소트 프로그램2&#x20;

#### Question - 1517

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2FGuQrQ0AtmmXAeQg9xihV%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-06-08%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%2012.44.39.png?alt=media\&token=210146fd-8cab-4de7-b9c4-5b3104a39418)

#### Code

```java
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    public static int[] A, tmp;
    public static long result;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        A = new int[N + 1];
        tmp = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for (int i = 1; i <= N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        result = 0;
        merget_sort(1, N);
        System.out.println(result);
    }
    
    private static void merget_sort(int s, int e) {
        if(e - s < 1)
            return;
        int m = s + (e - s) / 2;
        
        // 재귀 함수 형태로 구현하기
        merget_sort(s, m);
        merget_sort(m + 1, e);
        for (int i = s; i <= e; i++){
            tmp[i] = A[i];
        }
        
        int k = s;
        int index1 = s;
        int index2 = m + 1;
        while(index1 <= m && index2 <= e) { // 두 그룹을 병합하는 로직
            if(tmp[index1] > tmp[index2]) {
                A[k] = tmp[index2];
                result = result + index2 - k;
                k++;
                index2++;
            } else {
                A[k] = tmp[index1];
                k++;
                index1++;
            }
        }
        
        while (index1 <= m) {
            A[k] = tmp[index1];
            k++;
            index1++;
            
        }
        
        while (index2 <= e) {
            A[k] = tmp[index2];
            k++;
            index2++;
        }
    }
}
```

#### Insight

#### Idea

#### reference
