import java.util.*;
import java.lang.*;
import java.io.*;

class Sort {
    public List<Integer> mSort(List<Integer> items) {
        if (items.size() < 2) {
            return items;
        }
        
        List<Integer> a = mSort(items.subList(0, items.size()/2));
        List<Integer> b = mSort(items.subList(items.size()/2, items.size()));
        
        return merge(a, b);
    }

    public List<Integer> merge(List<Integer> a, List<Integer> b) {
        List<Integer> result = new ArrayList<>();
        
        int i = 0, j = 0;
        while (i < a.size() && j < b.size()) {
            if (a.get(i) < b.get(j)) {
                result.add(a.get(i));
                i++;
            } else {
                result.add(b.get(j));
                j++;
            }
        }
        
        while (i < a.size()) {
            result.add(a.get(i));
            i++;
        }
        while (j < b.size()) {
            result.add(b.get(j));
            j++;
        }
        
        return result;
    }
}

class Main {
    public static void main(String[] args) {
        List<Integer> items = new ArrayList<>(
            List.of(8,4,7,3,6,2,5,1)    
        );
        System.out.println(items);
        Sort sort = new Sort();
        System.out.println(sort.mSort(items));
    }    
}