Кухня(); Второй сезон - 79/79

import java.util.*;

public class Test {

    public static void main(String[] args) {
        int[] arr = initArr(30);
        System.out.println("init array");
        System.out.println(Arrays.toString(arr));
        arr = doSort(arr);
        System.out.println(Arrays.toString(arr));
        Arrays.sort(arr);//Для праверки работы
        System.out.println(Arrays.toString(arr));

//        int[] arr = initArr(1_000_000);
//        long t;
//        System.out.println("Start");
//        t = System.currentTimeMillis();
//        arr = doSort(arr);
//        System.out.println("time - " + (System.currentTimeMillis() - t) + " ms");
    }

    private static int[] doSort(int[] arr) {
        if (arr.length < 2) return arr;

        if (arr.length > 2) {
            int m = arr.length / 2;
            return merge(
                    doSort(Arrays.copyOfRange(arr, 0, m)),
                    doSort(Arrays.copyOfRange(arr, m, arr.length))
            );
        }

        if (arr[1] <= arr[0]) {
            int tmp = arr[0];
            arr[0] = arr[1];
            arr[1] = tmp;
        }

        return arr;
    }

    private static int[] merge(int[] arr1, int[] arr2) {
        int l = 0, r = 0;
        int[] result = new int[arr1.length + arr2.length];

        while (l < arr1.length && r < arr2.length)
            if (arr1[l] <= arr2[r]) result[l + r] = arr1[l++];
            else result[l + r] = arr2[r++];

        while (l < arr1.length) result[l + r] = arr1[l++];
        while (r < arr2.length) result[l + r] = arr2[r++];

        return result;
    }

    private static int[] initArr(int len) {
        int[] result = new int[len];
        for (int i = 0; i < result.length; i++) {
            result[i] = (int) (Math.random() * (5 + i));
            if (Math.random() < 0.5) result[i] *= -1;
        }