package io.github.tdudzik.algorithms.sorting;

import java.util.Arrays;

public class MergeSort implements SortingAlgorithm {

    public static void main(String[] args) {
        int[] elements = new int[] {1, 3, 2, 4};
        mergeSort(elements, 0, 3);
        System.out.println(Arrays.toString(elements));
    }

    @Override
    public void sort(int[] elements) {

    }

    private static void mergeSort(int[] elements, int p, int r) {
        if (p < r) {
            int q = (p + r) / 2;
            mergeSort(elements, p, q);
            mergeSort(elements, q + 1, r);
            merge(elements, p, q, r);
        }
    }

    private static void merge(int[] elements, int p, int q, int r) {
        int n1 = q - p + 1;
        int n2 = r - q;

        int[] left = new int[n1];
        for (int i = 0; i < n1; i++) {
            left[i] = elements[p + i];
        }

        int[] right = new int[n2];
        for (int i = 0; i < n2; i++) {
            right[i] = elements[q + i + 1];
        }

        int i = 0;
        int j = 0;
        int k = 0;
        while (i < n1 && j < n2) {
            if (left[i] <= right[j]) {
                elements[k++] = left[i++];
            } else {
                elements[k++] = right[j++];
            }
        }

        while (i < n1) {
            elements[k++] = left[i++];
        }

        while (j < n2) {
            elements[k++] = right[j++];
        }
    }

}