<jupyter_start><jupyter_text>Mergesort<jupyter_code>public class MergeSort {
    
                                //  java -ea NameOfProgram
    public static boolean isSorted(Comparable[] a, int low, int high) {
        if (low == high) {
            return true;
        }
        for(int i = low; i < high; i++) {
            if (less(a[i],a[i++]) == false) {
                return false;
            }
        }    
        return true;
    }
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }
    
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = aux[i];
        aux[i] = a[j];
        aux[j] = t;
    }
    public static void sort(Comparable[] a, Comparable[] aux,int lo, int hi) {
        if(hi <= lo) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        sort(a,aux, lo, mid);
        sort(a,aux, mid +1 ,hi);
        merge(a,aux,lo,mid,hi);
    }
    
    public static void sort(Comparable[] a) {
        Comparable[] aux = new Comparable[a.length];  // an array that implements interface Comparable
        sort(a,aux,0,a.length -1);
    }

    public static void merge(Comparable[] a, Comparable[] aux,int lo, int mid, int hi) {
        int i = lo; 
        int j= mid+1;
        
        assert isSorted(a,lo,mid);   // fail if sub arrays are not sorted
        assert isSorted(a,mid+1,hi);
        
        for(int k = lo; k <= hi; k++) {
            aux[k] = a[k];      // copy the elements into aux array
        }
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                a[k] = aux[j++];
            }
            else if(j > hi) {
                a[k] = aux[i++];
            }
            else if(less(aux[j] , aux[i])) {
                a[k] = aux[j++];
            }
            else {
                a[k] = aux[i++];
            }
            
        }
        assert isSorted(a,lo,hi);
    }
}<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.13940613990941117, 'fraction_numerical': 0.0035228988424760945, 'mean_word_length': 1.3723150357995226, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '159097', 'license': 'MIT', 'n_tokens_mistral': 665, 'n_tokens_neox': 653, 'n_words': 174, 'path': 'mergesort.ipynb', 'repo_name': 'andrewdonov/java_algo_notebooks', 'size': '1987'}