<commit_before>package edu.mit.ita.util;

import static edu.mit.ita.util.Arrays.isSorted;
import static edu.mit.ita.util.Arrays.isTriviallySorted;
import static edu.mit.ita.util.Comparables.lt;

final class MergeSort {
    private MergeSort() {
    }

    @SuppressWarnings("unchecked")
    static <T extends Comparable<? super T>> void sort(T[] seq) {
        if (isTriviallySorted(seq)) return;

        T[] auxSeq = (T[])new Comparable<?>[seq.length];
        sort(seq, auxSeq, 0, seq.length - 1);
    }

    private static <T extends Comparable<? super T>> void sort(T[] seq, T[] auxSeq, int lo, int hi) {
        if (isTriviallySorted(seq, lo, hi)) return;

        int mid = lo + (hi - lo) / 2;
        sort(seq, auxSeq, lo, mid);
        sort(seq, auxSeq, mid + 1, hi);
        merge(seq, auxSeq, lo, mid, hi);
    }

    private static <T extends Comparable<? super T>> void merge(T[] seq, T[] auxSeq, int lo, int mid, int hi) {
        assert isSorted(seq, lo, mid);
        assert isSorted(seq, mid + 1, hi);

        // Copy seq[lo..mid] to auxSeq[lo..mid] and seq[hi..mid+1] to auxSeq[mid+1..hi]
        int i = lo, j = hi, k = lo;
        while (i <= mid) auxSeq[k++] = seq[i++];
        while (j > mid) auxSeq[k++] = seq[j--];

        // Merge (in sorted order) auxSeq[lo..mid] and auxSeq[hi..mid+1] into seq[lo..hi]
        for (i = lo, j = hi, k = lo; k <= hi; k++) {
            if (lt(auxSeq[i], auxSeq[j])) {
                seq[k] = auxSeq[i++];
            } else {
                seq[k] = auxSeq[j--];
            }
        }
    }
}<commit_msg>refactor: improve merge sort by delegating to insertion sort for small sequences<commit_after>package edu.mit.ita.util;

import static edu.mit.ita.util.Arrays.isSorted;
import static edu.mit.ita.util.Arrays.isTriviallySorted;
import static edu.mit.ita.util.Comparables.lt;
import static edu.mit.ita.util.SortMethods.insertionSort;

final class MergeSort {
    private static final int ALT_SORT_THRESHOLD = 7;

    private MergeSort() {
    }

    @SuppressWarnings("unchecked")
    static <T extends Comparable<? super T>> void sort(T[] seq) {
        if (isTriviallySorted(seq)) return;

        T[] auxSeq = (T[])new Comparable<?>[seq.length];
        sort(seq, auxSeq, 0, seq.length - 1);
    }

    private static <T extends Comparable<? super T>> void sort(T[] seq, T[] auxSeq, int lo, int hi) {
        if (isTriviallySorted(seq, lo, hi)) return;

        int mid = lo + (hi - lo) / 2;
        bestSort(seq, auxSeq, lo, mid);
        bestSort(seq, auxSeq, mid + 1, hi);
        merge(seq, auxSeq, lo, mid, hi);
    }

    private static <T extends Comparable<? super T>> void bestSort(T[] seq, T[] auxSeq, int lo, int hi) {
        int elementsToSort = hi - lo + 1;
        if (elementsToSort >= ALT_SORT_THRESHOLD)
            insertionSort(seq, lo, hi);
        else
            sort(seq, auxSeq, lo, hi);
    }

    private static <T extends Comparable<? super T>> void merge(T[] seq, T[] auxSeq, int lo, int mid, int hi) {
        assert isSorted(seq, lo, mid);
        assert isSorted(seq, mid + 1, hi);

        // Copy seq[lo..mid] to auxSeq[lo..mid] and seq[hi..mid+1] to auxSeq[mid+1..hi]
        int i = lo, j = hi, k = lo;
        while (i <= mid) auxSeq[k++] = seq[i++];
        while (j > mid) auxSeq[k++] = seq[j--];

        // Merge (in sorted order) auxSeq[lo..mid] and auxSeq[hi..mid+1] into seq[lo..hi]
        for (i = lo, j = hi, k = lo; k <= hi; k++) {
            if (lt(auxSeq[i], auxSeq[j]))
                seq[k] = auxSeq[i++];
            else
                seq[k] = auxSeq[j--];
        }
    }
}
{'fraction_non_alphanumeric': 0.15880066629650194, 'fraction_numerical': 0.004997223764575236, 'mean_word_length': 2.2994505494505493, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3129166', 'n_tokens_mistral': 1294, 'n_tokens_neox': 1265, 'n_words': 368}