package com.company;

import java.util.Random;

/**
 * Zadanie 1, mergesort
 */
public class Main {

    private static class Mergesort
    {
        private int[] numbers;
        private int[] helper;
        private int number;

        public void sort(int[] values) {
            numbers = values;
            number = values.length;
            helper = new int[number];

        }

        private void mergesort(int low, int high)
        {
            //sprawdz czy zmienna low jest mniejsza niz high jesli nie to tablica jest juz posortowana
            if(low < high)
            {
                //pobierz element po srodku
                int middle = low + (high - low) / 2;
                //sortuj lewa czesc tablicy
                mergesort(low, middle);
                //sortuj prawa czesc tablicy
                mergesort(middle + 1, high);
                //polacz oba wyniki
                merge(low, middle, high);
            }
        }

        private void merge(int low, int middle, int high)
        {
            for(int i = low; i <= high; i++)
            {
                helper[i] = numbers[i];
            }

            int i = low;
            int j = middle + 1;
            int k = low;

            while(i <= middle && j <= high)
            {
                if(helper[i] <= helper[j])
                {
                    numbers[k] = helper[i];
                    i++;
                }else{
                    numbers[k] = helper[j];
                    j++;
                }
                k++;
            }

            while(i <= middle)
            {
                numbers[k] = helper[i];
                k++;
                i++;
            }
        }
    }

    private static int[] generateRandomNumbers(int size)
    {
        int[] numbers = new int[size];
        Random randomGenerator = new Random();
        for(int i = 0; i < numbers.length; i++)
            numbers[i] = randomGenerator.nextInt();

        return numbers;
    }

    public static void main(String[] args) {

        long startTime = System.currentTimeMillis();
        Mergesort mergesort = new Mergesort();

        int[] numbers = generateRandomNumbers(6000000);
        mergesort.sort(numbers);

        long stopTime = System.currentTimeMillis();
        long elapsedTime = stopTime - startTime;

        System.out.println("Elapsed time: " +  elapsedTime);


    }
}