<commit_before>// Time:  O(nlogn)
// Space: O(n)

// Merge sort.
class Solution {
public:
    /**
     * @param A an integer array
     * @return void
     */
    void sortIntegers2(vector<int>& A) {
        mergeSort(&A, 0, A.size() - 1);
    }

private:
    void mergeSort(vector<int> *A, int start, int end) {
        if (end - start <= 0) {
            return;
        }
        int mid = start + (end - start) / 2;
        mergeSort(A, start, mid);
        mergeSort(A, mid + 1, end);

        int l = start;
        vector<int> tmp;
        for (int i = mid + 1; i <= end; ++i) {
            // Merge the two sorted arrays into tmp.
            while (l <= mid && (*A)[l] <= (*A)[i]) {
                tmp.emplace_back((*A)[l++]);
            }
            tmp.emplace_back((*A)[i]);
        }
        while (l <= mid) {
            tmp.emplace_back((*A)[l++]);
        }
        // Copy tmp back to A.
        copy(tmp.begin(), tmp.end(), A->begin() + start);
    }
};

// Time:  O(nlogn) ~ O(n^2)
// Space: O(logn) ~ O(n)
// Quick sort.
class Solution {
public:
    /**<commit_msg>Update sort-integers-ii.cpp<commit_after>// Time:  O(nlogn)
// Space: O(n)

// Merge sort. (stable)
class Solution {
public:
    /**
     * @param A an integer array
     * @return void
     */
    void sortIntegers2(vector<int>& A) {
        mergeSort(&A, 0, A.size() - 1);
    }

private:
    void mergeSort(vector<int> *A, int start, int end) {
        if (end - start <= 0) {
            return;
        }
        int mid = start + (end - start) / 2;
        mergeSort(A, start, mid);
        mergeSort(A, mid + 1, end);

        int l = start;
        vector<int> tmp;
        for (int i = mid + 1; i <= end; ++i) {
            // Merge the two sorted arrays into tmp.
            while (l <= mid && (*A)[l] <= (*A)[i]) {
                tmp.emplace_back((*A)[l++]);
            }
            tmp.emplace_back((*A)[i]);
        }
        while (l <= mid) {
            tmp.emplace_back((*A)[l++]);
        }
        // Copy tmp back to A.
        copy(tmp.begin(), tmp.end(), A->begin() + start);
    }
};

// Time:  O(nlogn) ~ O(n^2)
// Space: O(logn) ~ O(n)
// Quick sort. (unstable)
class Solution {
public:
    /**
{'fraction_non_alphanumeric': 0.18670886075949367, 'fraction_numerical': 0.007233273056057866, 'mean_word_length': 1.5822637106184365, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 11, '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': '5182201', 'n_tokens_mistral': 804, 'n_tokens_neox': 780, 'n_words': 205}