1
//递归实现归并排序
2
public class Main {
3

4
    public static int[] arr = new int[200];
5
    public static int[] help = new int[200];
6
    public static int n;
7

8
    public static void main(String[] args) throws IOException {
9

10
    }
11
    public static void gb (int l ,int r) {
12
        if (l == r) {
13
            return;
14
        }
15
        int m = (l + r) / 2;
16
        gb (l ,m);
17
        gb (m + 1 ,r);
18
        mergeArr (l ,m ,r);
19
    }
20

21
    private static void mergeArr(int l, int m, int r) {
22
        int left = l ,right = m + 1 ,flag = l;
23
        while (left <= m && right <= r) {
24
            if (arr[left] <= arr[right]) {
25
                help[flag ++] = arr[left ++];
26
            }
27
            else {
28
                help[flag ++] = arr[right ++];
29
            }
30
        }
31
        while (left <= m) help[flag ++] = arr[left ++];
32
        while (right <= r) help[flag ++] = arr[right ++];
33

34
        for (int i = l ;i <= r ;i ++) {
35
            arr[i] = help[i];
36
        }
37
    }
38
}

1
package org.example;
2

3
import java.io.*;
4

5
//非递归实现归并排序
6
public class Main {
7

8
    public static int[] arr = new int[200];
9
    public static int[] help = new int[200];
10
    public static int n;
11

12
    public static void main(String[] args) throws IOException {
13

14
    }
15
    public static void gb () {
16
        if (n <= 1) return;
17

18
        for (int l ,r ,mid ,step = 1 ;step < n ;step <<= 1) {
19
            l = 0;
20
            while (l < n) {
21
                mid = l + step - 1;
22
                if (mid + 1 >= n) break;//没有右侧值，直接结束本轮循环
23
                r = Math.min(l + 2 * step - 1 ,n - 1);//注意，右侧的右边界可能长度与左侧相等，也可能长度不够了
24
                mergeArr(l ,mid ,r);
25
                l = r + 1;
26
            }
27
        }
28
    }
29

30
    private static void mergeArr(int l, int m, int r) {
31
        int left = l ,right = m + 1 ,flag = l;
32
        while (left <= m && right <= r) {
33
            if (arr[left] <= arr[right]) {
34
                help[flag ++] = arr[left ++];
35
            }
36
            else {
37
                help[flag ++] = arr[right ++];
38
            }
39
        }
40
        while (left <= m) help[flag ++] = arr[left ++];
41
        while (right <= r) help[flag ++] = arr[right ++];
42

43
        for (int i = l ;i <= r ;i ++) {
44
            arr[i] = help[i];
45
        }
46
    }
47
}