<commit_before>// Parallel mergesort: regular sorting with a parallel merge step.
// O(n log n) time; O(n) extra space; critical path is O(log^3 n)
//
// Algorithm described in: https://software.intel.com/en-us/articles/a-parallel-stable-sort-using-c11-for-tbb-cilk-plus-and-openmp
extern crate rayon;

use std::cmp::max;
use std::env::args;
use std::time::Instant;

pub fn merge_sort<T: Ord + Send + Copy>(v: &mut [T]) {
    let n = v.len();
    let mut buf = Vec::with_capacity(n);
    // We always overwrite the buffer before reading to it, and letting rust
    // initialize it would increase the critical path to O(n).
    unsafe {
        buf.set_len(n);
    }
    rsort(v, &mut buf[..]);
}

// Values from manual tuning gigasort on one machine.
const SORT_CHUNK: usize = 32 * 1024;
const MERGE_CHUNK: usize = 64 * 1024;

// Sort src, possibly making use of identically sized buf.
fn rsort<T: Ord + Send + Copy>(src: &mut [T], buf: &mut [T]) {
    if src.len() <= SORT_CHUNK {
        src.sort();
        return;
    }

    // Sort each half into half of the buffer.
    let mid = src.len() / 2;
    let (bufa, bufb) = buf.split_at_mut(mid);
    {
        let (sa, sb) = src.split_at_mut(mid);
        rayon::join(|| rsort_into(sa, bufa), || rsort_into(sb, bufb));
    }

    // Merge the buffer halves back into the original.
    rmerge(bufa, bufb, src);
}

// Sort src, putting the result into dest.
fn rsort_into<T: Ord + Send + Copy>(src: &mut [T], dest: &mut [T]) {
    let mid = src.len() / 2;
    let (s1, s2) = src.split_at_mut(mid);
    {
        // Sort each half.
        let (d1, d2) = dest.split_at_mut(mid);
        rayon::join(|| rsort(s1, d1), || rsort(s2, d2));
    }

    // Merge the halves into dest.
    rmerge(s1, s2, dest);
}

// Merge sorted inputs a and b, putting result in dest.
// TODO: Figure out how to get a and b immutable with enough template magic.
fn rmerge<T: Ord + Send + Copy>(a: &mut [T], b: &mut [T], dest: &mut [T]) {
    // Swap so a is always longer.
    let (a, b) = if a.len() > b.len() {
        (a, b)
    } else {
        (b, a)
    };
    if dest.len() <= MERGE_CHUNK {
        seq_merge(a, b, dest);
        return;
    }

    // Find the middle element of the longer list, and
    // use binary search to find its location in the shorter list.
    let ma = a.len() / 2;
    let mb = match b.binary_search(&a[ma]) {
        Ok(i) => i,<commit_msg>adjust comment<commit_after>// Parallel mergesort: regular sorting with a parallel merge step.
// O(n log n) time; O(n) extra space; critical path is O(log^3 n)
//
// Algorithm described in: https://software.intel.com/en-us/articles/a-parallel-stable-sort-using-c11-for-tbb-cilk-plus-and-openmp
extern crate rayon;

use std::cmp::max;
use std::env::args;
use std::time::Instant;

pub fn merge_sort<T: Ord + Send + Copy>(v: &mut [T]) {
    let n = v.len();
    let mut buf = Vec::with_capacity(n);
    // We always overwrite the buffer before reading to it, and letting rust
    // initialize it would increase the critical path to O(n).
    unsafe {
        buf.set_len(n);
    }
    rsort(v, &mut buf[..]);
}

// Values from manual tuning gigasort on one machine.
const SORT_CHUNK: usize = 32 * 1024;
const MERGE_CHUNK: usize = 64 * 1024;

// Sort src, possibly making use of identically sized buf.
fn rsort<T: Ord + Send + Copy>(src: &mut [T], buf: &mut [T]) {
    if src.len() <= SORT_CHUNK {
        src.sort();
        return;
    }

    // Sort each half into half of the buffer.
    let mid = src.len() / 2;
    let (bufa, bufb) = buf.split_at_mut(mid);
    {
        let (sa, sb) = src.split_at_mut(mid);
        rayon::join(|| rsort_into(sa, bufa), || rsort_into(sb, bufb));
    }

    // Merge the buffer halves back into the original.
    rmerge(bufa, bufb, src);
}

// Sort src, putting the result into dest.
fn rsort_into<T: Ord + Send + Copy>(src: &mut [T], dest: &mut [T]) {
    let mid = src.len() / 2;
    let (s1, s2) = src.split_at_mut(mid);
    {
        // Sort each half.
        let (d1, d2) = dest.split_at_mut(mid);
        rayon::join(|| rsort(s1, d1), || rsort(s2, d2));
    }

    // Merge the halves into dest.
    rmerge(s1, s2, dest);
}

// Merge sorted inputs a and b, putting result in dest.
//
// Note: `a` and `b` have type `&mut [T]` and not `&[T]` because we do
// not want to require a `T: Sync` bound. Using `&mut` references
// proves to the compiler that we are not sharing `a` and `b` across
// threads and thus we only need a `T: Send` bound.
fn rmerge<T: Ord + Send + Copy>(a: &mut [T], b: &mut [T], dest: &mut [T]) {
    // Swap so a is always longer.
    let (a, b) = if a.len() > b.len() {
        (a, b)
    } else {
        (b, a)
    };
    if dest.len() <= MERGE_CHUNK {
        seq_merge(a, b, dest);
        return;
    }

    // Find the middle element of the longer list, and
    // use binary search to find its location in the shorter list.
    let ma = a.len() / 2;
    let mb = match b.binary_search(&a[ma]) {
        Ok(i) => i,
{'fraction_non_alphanumeric': 0.15467842115808456, 'fraction_numerical': 0.011220196353436185, 'mean_word_length': 2.4933519944016793, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 15, 'https://': 2, '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': '5903327', 'n_tokens_mistral': 1860, 'n_tokens_neox': 1807, 'n_words': 614}