notriddle · Aug 26, 2020 · Aug 27, 2020 · Aug 27, 2020 · Aug 27, 2020 · Aug 27, 2020
diff --git a/.github/workflows/ci.yaml b/.github/workflows/ci.yaml
@@ -0,0 +1,30 @@
+on:
+  pull_request:
+  push:
+    branches: [master]
+
+jobs:
+  build_test:
+    runs-on: ubuntu-latest
+
+    steps:
+      - uses: actions/checkout@v2
+      - name: Test (debug)
+        uses: actions-rs/cargo@v1
+        with:
+          command: test
+      - name: Test (release)
+        uses: actions-rs/cargo@v1
+        with:
+          command: test
+          args: --release
+      - name: Check rustfmt
+        uses: actions-rs/cargo@v1
+        with:
+          command: fmt
+          args: -- --check
+      - name: Check clippy
+        uses: actions-rs/cargo@v1
+        with:
+          command: clippy
+          args: --tests -- -Dwarnings
diff --git a/.travis.yml b/.travis.yml
diff --git a/Cargo.toml b/Cargo.toml
@@ -1,8 +1,12 @@
 [package]
 name = "timsort"
-version = "0.1.0"
-authors = ["Michael Howell <michael@notriddle.com>"]
+version = "0.1.3"
+description = "Rust implementation of the modified MergeSort used in Python and Java"
+repository = "https://github.com/RustPython/rust-timsort"
+authors = ["Michael Howell <michael@notriddle.com>", "RustPython Team"]
+license = "MIT/Apache-2.0"
+edition = "2018"
 
 [dev-dependencies]
-rand = "0.3.9"
+rand = { version = "0.8", features = ["small_rng"] }
 
diff --git a/LICENSE-MIT b/LICENSE-MIT
@@ -1,4 +1,5 @@
 Copyright (c) 2015 Michael Howell
+Portions (c) 2020 RustPython Team
 
 Permission is hereby granted, free of charge, to any person obtaining a copy
 of this software and associated documentation files (the "Software"), to deal

diff --git a/benches/bench.rs b/benches/bench.rs
@@ -3,24 +3,26 @@
 #![feature(test)]
 #![feature(unboxed_closures)]
 
-extern crate timsort;
 extern crate test;
-extern crate rand;
 
-use timsort::sort;
-use rand::{weak_rng, Rng};
+use rand::{distributions::Standard, prelude::SmallRng, seq::SliceRandom, Rng, SeedableRng};
 use std::mem;
 use test::Bencher;
+use timsort::sort;
+
+type BigSortable = (u64, u64, u64, u64);
 
-type BigSortable = (u64,u64,u64,u64);
+fn rng() -> impl Rng {
+    SmallRng::from_entropy()
+}
 
 macro_rules! bench_random(
     ($name: ident, $sortfun: ident, $typ: ty, $n: expr) => (
         #[bench]
         fn $name(b: &mut Bencher) {
-            let mut rng = weak_rng();
+            let mut rng = rng();
             b.iter(|| {
-                let mut v = rng.gen_iter::<$typ>().take($n).collect::<Vec<$typ>>();
+                let mut v = (&mut rng).sample_iter(Standard).take($n).collect::<Vec<$typ>>();
                 $sortfun(&mut v[..]);
             });
             b.bytes = $n * mem::size_of::<$typ>() as u64;
@@ -42,7 +44,7 @@ bench_random!(sort_big_random_large, sort, BigSortable, 10_000);
 
 #[bench]
 fn sort_sorted(b: &mut Bencher) {
-    let mut v: Vec<_> = (0 .. 10000isize).collect();
+    let mut v: Vec<_> = (0..10000isize).collect();
     b.iter(|| {
         sort(&mut v[..]);
     });
@@ -51,7 +53,7 @@ fn sort_sorted(b: &mut Bencher) {
 
 #[bench]
 fn sort_big_sorted(b: &mut Bencher) {
-    let mut v: Vec<_> = (0 .. 10000usize).map(|i| (i, i, i, i)).collect();
+    let mut v: Vec<_> = (0..10000usize).map(|i| (i, i, i, i)).collect();
     b.iter(|| {
         sort(&mut v[..]);
     });
@@ -61,14 +63,14 @@ fn sort_big_sorted(b: &mut Bencher) {
 #[bench]
 fn sort_few_unique(b: &mut Bencher) {
     let mut v = Vec::new();
-    for i in (0u32 .. 10) {
-        for _ in (0usize .. 100) {
+    for i in 0u32..10 {
+        for _ in 0usize..100 {
             v.push(i);
         }
     }
-    let mut rng = weak_rng();
-    b.iter(||{
-        rng.shuffle(&mut v[..]);
+    let mut rng = rng();
+    b.iter(|| {
+        v.shuffle(&mut rng);
         sort(&mut v[..]);
     });
     b.bytes = (v.len() * mem::size_of_val(&v[0])) as u64;
@@ -85,31 +87,41 @@ fn sort_equals(b: &mut Bencher) {
 
 #[bench]
 fn sort_huge(b: &mut Bencher) {
-    let mut rng = weak_rng();
+    let mut rng = rng();
     let n = 100_000;
-    let mut v = rng.gen_iter::<i64>().take(n).collect::<Vec<i64>>();
+    let mut v = (&mut rng)
+        .sample_iter(Standard)
+        .take(n)
+        .collect::<Vec<i64>>();
     b.iter(|| {
-        rng.shuffle(&mut v[..]);
+        v.shuffle(&mut rng);
         sort(&mut v[..]);
     });
     b.bytes = (n * mem::size_of::<i64>()) as u64;
 }
 
 #[bench]
 fn sort_partially_sorted(b: &mut Bencher) {
-    fn partially_sort<T: Ord+::std::fmt::Display>(v: &mut [T]) {
+    fn partially_sort<T: Ord + ::std::fmt::Display>(v: &mut [T]) {
         let s = v.len() / 100;
-        if s == 0 { return; }
+        if s == 0 {
+            return;
+        }
         let mut sorted = true;
         for c in v.chunks_mut(s) {
-            if sorted { sort(&mut c[..]); }
+            if sorted {
+                sort(&mut c[..]);
+            }
             sorted = !sorted;
         }
     }
-    let mut rng = weak_rng();
+    let mut rng = rng();
     let n = 10_000;
-    let mut v = rng.gen_iter::<i64>().take(n).collect::<Vec<i64>>();
-    rng.shuffle(&mut v[..]);
+    let mut v = (&mut rng)
+        .sample_iter(Standard)
+        .take(n)
+        .collect::<Vec<i64>>();
+    v.shuffle(&mut rng);
     partially_sort(&mut v[..]);
     b.iter(|| {
         let mut v2 = v.clone();
@@ -120,26 +132,26 @@ fn sort_partially_sorted(b: &mut Bencher) {
 
 #[bench]
 fn sort_strings(b: &mut Bencher) {
-    let mut rng = weak_rng();
+    let mut rng = rng();
     let n = 10_000usize;
     let mut v = Vec::with_capacity(n);
     let mut bytes = 0;
-    for _ in (0 .. n) {
-        let len = rng.gen_range(0, 60);
+    for _ in 0..n {
+        let len = rng.gen_range(0..=60);
         bytes += len;
         let mut s = String::with_capacity(len);
         if len == 0 {
             v.push(s);
             continue;
         }
-        for _ in (0 .. len) {
-            s.push(rng.gen_range(b'a', b'z') as char);
+        for _ in 0..len {
+            s.push(rng.gen_range(b'a'..=b'z') as char);
         }
         v.push(s);
     }
 
     b.iter(|| {
-        rng.shuffle(&mut v[..]);
+        v.shuffle(&mut rng);
         sort(&mut v[..]);
     });
     b.bytes = bytes as u64;

diff --git a/benches/bench_default.rs b/benches/bench_default.rs
@@ -3,28 +3,30 @@
 #![feature(test)]
 #![feature(unboxed_closures)]
 
-extern crate timsort;
 extern crate test;
-extern crate rand;
 
-use rand::{weak_rng, Rng};
+use rand::{distributions::Standard, rngs::SmallRng, seq::SliceRandom, Rng, SeedableRng};
 use std::mem;
 use test::Bencher;
 
+fn rng() -> impl Rng {
+    SmallRng::from_entropy()
+}
+
 #[inline]
 fn sort<T: Ord>(l: &mut [T]) {
     l.sort();
 }
 
-type BigSortable = (u64,u64,u64,u64);
+type BigSortable = (u64, u64, u64, u64);
 
 macro_rules! bench_random(
     ($name: ident, $sortfun: ident, $typ: ty, $n: expr) => (
         #[bench]
         fn $name(b: &mut Bencher) {
-            let mut rng = weak_rng();
+            let mut rng = rng();
             b.iter(|| {
-                let mut v = rng.gen_iter::<$typ>().take($n).collect::<Vec<$typ>>();
+                let mut v = (&mut rng).sample_iter(Standard).take($n).collect::<Vec<$typ>>();
                 $sortfun(&mut v[..]);
             });
             b.bytes = $n * mem::size_of::<$typ>() as u64;
@@ -46,7 +48,7 @@ bench_random!(sort_big_random_large, sort, BigSortable, 10_000);
 
 #[bench]
 fn sort_sorted(b: &mut Bencher) {
-    let mut v: Vec<_> = (0 .. 10000isize).collect();
+    let mut v: Vec<_> = (0..10000isize).collect();
     b.iter(|| {
         sort(&mut v[..]);
     });
@@ -55,7 +57,7 @@ fn sort_sorted(b: &mut Bencher) {
 
 #[bench]
 fn sort_big_sorted(b: &mut Bencher) {
-    let mut v: Vec<_> = (0 .. 10000usize).map(|i| (i, i, i, i)).collect();
+    let mut v: Vec<_> = (0..10000usize).map(|i| (i, i, i, i)).collect();
     b.iter(|| {
         sort(&mut v[..]);
     });
@@ -65,14 +67,14 @@ fn sort_big_sorted(b: &mut Bencher) {
 #[bench]
 fn sort_few_unique(b: &mut Bencher) {
     let mut v = Vec::new();
-    for i in (0u32 .. 10) {
-        for _ in (0usize .. 100) {
+    for i in 0u32..10 {
+        for _ in 0usize..100 {
             v.push(i);
         }
     }
-    let mut rng = weak_rng();
-    b.iter(||{
-        rng.shuffle(&mut v[..]);
+    let mut rng = rng();
+    b.iter(|| {
+        v.shuffle(&mut rng);
         sort(&mut v[..]);
     });
     b.bytes = (v.len() * mem::size_of_val(&v[0])) as u64;
@@ -89,31 +91,41 @@ fn sort_equals(b: &mut Bencher) {
 
 #[bench]
 fn sort_huge(b: &mut Bencher) {
-    let mut rng = weak_rng();
+    let mut rng = rng();
     let n = 100_000;
-    let mut v = rng.gen_iter::<i64>().take(n).collect::<Vec<i64>>();
+    let mut v = (&mut rng)
+        .sample_iter(Standard)
+        .take(n)
+        .collect::<Vec<i64>>();
     b.iter(|| {
-        rng.shuffle(&mut v[..]);
+        v.shuffle(&mut rng);
         sort(&mut v[..]);
     });
     b.bytes = (n * mem::size_of::<i64>()) as u64;
 }
 
 #[bench]
 fn sort_partially_sorted(b: &mut Bencher) {
-    fn partially_sort<T: Ord+::std::fmt::Display>(v: &mut [T]) {
+    fn partially_sort<T: Ord + ::std::fmt::Display>(v: &mut [T]) {
         let s = v.len() / 100;
-        if s == 0 { return; }
+        if s == 0 {
+            return;
+        }
         let mut sorted = true;
         for c in v.chunks_mut(s) {
-            if sorted { sort(&mut c[..]); }
+            if sorted {
+                sort(&mut c[..]);
+            }
             sorted = !sorted;
         }
     }
-    let mut rng = weak_rng();
+    let mut rng = rng();
     let n = 10_000;
-    let mut v = rng.gen_iter::<i64>().take(n).collect::<Vec<i64>>();
-    rng.shuffle(&mut v[..]);
+    let mut v = (&mut rng)
+        .sample_iter(Standard)
+        .take(n)
+        .collect::<Vec<i64>>();
+    v.shuffle(&mut rng);
     partially_sort(&mut v[..]);
     b.iter(|| {
         let mut v2 = v.clone();
@@ -124,26 +136,26 @@ fn sort_partially_sorted(b: &mut Bencher) {
 
 #[bench]
 fn sort_strings(b: &mut Bencher) {
-    let mut rng = weak_rng();
+    let mut rng = rng();
     let n = 10_000usize;
     let mut v = Vec::with_capacity(n);
     let mut bytes = 0;
-    for _ in (0 .. n) {
-        let len = rng.gen_range(0, 60);
+    for _ in 0..n {
+        let len = rng.gen_range(0..=60);
         bytes += len;
         let mut s = String::with_capacity(len);
         if len == 0 {
             v.push(s);
             continue;
         }
-        for _ in (0 .. len) {
-            s.push(rng.gen_range(b'a', b'z') as char);
+        for _ in 0..len {
+            s.push(rng.gen_range(b'a'..=b'z') as char);
         }
         v.push(s);
     }
 
     b.iter(|| {
-        rng.shuffle(&mut v[..]);
+        v.shuffle(&mut rng);
         sort(&mut v[..]);
     });
     b.bytes = bytes as u64;

diff --git a/src/find_run.rs b/src/find_run.rs
@@ -0,0 +1,46 @@
+//! The run finder algorithm. Takes an unsorted slice, and returns the number
+//! of sequential elements in a row.
+
+#[cfg(test)]
+mod tests;
+
+use crate::Comparator;
+
+/// Find a run, reversing if necessary.
+pub(crate) fn get_run<T, C: Comparator<T>>(list: &mut [T], cmp: &C) -> Result<usize, C::Error> {
+    let (ord, len) = find_run(list, cmp)?;
+    if ord {
+        list[..len].reverse();
+    }
+    Ok(len)
+}
+
+/// Find a run. Returns true if it needs reversed, and false otherwise.
+pub(crate) fn find_run<T, C: Comparator<T>>(
+    list: &[T],
+    cmp: &C,
+) -> Result<(bool, usize), C::Error> {
+    let (first, second) = match list {
+        [a, b, ..] => (a, b),
+        _ => return Ok((false, list.len())),
+    };
+    let mut pos = 1;
+    let gt = if cmp.is_gt(first, second)? {
+        for pair in list[1..].windows(2) {
+            if !cmp.is_gt(&pair[0], &pair[1])? {
+                break;
+            }
+            pos += 1;
+        }
+        true
+    } else {
+        for pair in list[1..].windows(2) {
+            if cmp.is_gt(&pair[0], &pair[1])? {
+                break;
+            }
+            pos += 1;
+        }
+        false
+    };
+    Ok((gt, pos + 1))
+}
diff --git a/src/find_run/mod.rs b/src/find_run/mod.rs
diff --git a/src/find_run/tests.rs b/src/find_run/tests.rs
@@ -1,4 +1,4 @@
-use find_run;
+use crate::{comparator, never, ord_t_comparator};
 
 #[test]
 fn empty() {
@@ -10,14 +10,14 @@ fn empty() {
 
 #[test]
 fn single() {
-    let (ord, len) = find_run(&vec![1]);
+    let (ord, len) = find_run(&[1]);
     assert_eq!(ord, false);
     assert_eq!(len, 1);
 }
 
 #[test]
 fn greater() {
-    let (ord, len) = find_run(&vec![1, 2, 2, 3, 4, 5]);
+    let (ord, len) = find_run(&[1, 2, 2, 3, 4, 5]);
     assert_eq!(ord, false);
     assert_eq!(len, 6);
 }
@@ -26,21 +26,21 @@ fn greater() {
 // less ordering. Unfortunately, reversing those sub-runs creates an unstable sort.
 #[test]
 fn less_stable() {
-    let (ord, len) = find_run(&vec![5, 4, 4, 3, 4, 5]);
+    let (ord, len) = find_run(&[5, 4, 4, 3, 4, 5]);
     assert_eq!(ord, true);
     assert_eq!(len, 2);
 }
 
 #[test]
 fn less() {
-    let (ord, len) = find_run(&vec![5, 4, 3, 2, 1, 0]);
+    let (ord, len) = find_run(&[5, 4, 3, 2, 1, 0]);
     assert_eq!(ord, true);
     assert_eq!(len, 6);
 }
 
 #[test]
 fn equal() {
-    let (ord, len) = find_run(&vec![2, 2, 2, 2, 2, 2]);
+    let (ord, len) = find_run(&[2, 2, 2, 2, 2, 2]);
     assert_eq!(ord, false);
     assert_eq!(len, 6);
 }
@@ -69,15 +69,12 @@ fn get_run_noreverse() {
     assert_eq!(list[4], 7);
 }
 
-
 /// With comparator.
-pub fn find_run<T: Ord>(list: &[T]) -> (bool, usize) {
-    find_run::find_run(list, |a, b| a.cmp(b))
+fn find_run<T: Ord>(list: &[T]) -> (bool, usize) {
+    super::find_run(list, &comparator(|a, b| Ok(a > b))).unwrap_or_else(never)
 }
 
-
 /// With comparator.
-pub fn get_run<T: Ord>(list: &mut [T]) -> usize {
-    find_run::get_run(list, |a, b| a.cmp(b))
+fn get_run<T: Ord>(list: &mut [T]) -> usize {
+    super::get_run(list, &ord_t_comparator()).unwrap_or_else(never)
 }
-
diff --git a/src/gallop/mod.rs → src/gallop.rs b/src/gallop/mod.rs → src/gallop.rs
@@ -1,117 +1,126 @@
-//! The galloping search algorithm. 
+//! The galloping search algorithm.
 
 #[cfg(test)]
 mod tests;
 
-use std::cmp::Ordering;
+use crate::Comparator;
+use core::cmp::Ordering;
 
 #[derive(Copy, Clone)]
-pub enum Mode {
+pub(crate) enum Mode {
     Forward,
-    Reverse
+    Reverse,
 }
 
 /// Returns the index where key should be inserted, assuming it shoul be placed
 /// at the beginning of any cluster of equal items.
-pub fn gallop_left<T, C: Fn(&T, &T) -> Ordering>(key: &T, list: &[T], mode: Mode, c: C) -> usize {
-    let (mut base, mut lim) = gallop(key, list, mode, &c);
+pub(crate) fn gallop_left<T, C: Comparator<T>>(
+    key: &T,
+    list: &[T],
+    mode: Mode,
+    cmp: &C,
+) -> Result<usize, C::Error> {
+    let (mut base, mut lim) = gallop(key, list, mode, cmp)?;
     while lim != 0 {
         let ix = base + (lim / 2);
-        match c(&list[ix], key) {
+        match cmp.ordering(&list[ix], key)? {
             Ordering::Less => {
                 base = ix + 1;
                 lim -= 1;
-            },
+            }
             Ordering::Greater => (),
             Ordering::Equal => {
-                if ix == 0 || c(&list[ix - 1], key) == Ordering::Less {
+                if ix == 0 || cmp.is_gt(key, &list[ix - 1])? {
                     base = ix;
                     break;
                 }
-            },
+            }
         };
         lim /= 2;
     }
-    base
+    Ok(base)
 }
 
 /// Returns the index where key should be inserted, assuming it shoul be placed
 /// at the end of any cluster of equal items.
-pub fn gallop_right<T, C: Fn(&T, &T) -> Ordering>(key: &T, list: &[T], mode: Mode, c: C) -> usize {
+pub(crate) fn gallop_right<T, C: Comparator<T>>(
+    key: &T,
+    list: &[T],
+    mode: Mode,
+    cmp: &C,
+) -> Result<usize, C::Error> {
     let list_len = list.len();
-    let (mut base, mut lim) = gallop(key, list, mode, &c);
+    let (mut base, mut lim) = gallop(key, list, mode, cmp)?;
     while lim != 0 {
         let ix = base + (lim / 2);
-        match c(&list[ix], key) {
+        match cmp.ordering(&list[ix], key)? {
             Ordering::Less => {
                 base = ix + 1;
                 lim -= 1;
-            },
+            }
             Ordering::Greater => (),
             Ordering::Equal => {
                 base = ix + 1;
-                if ix == list_len - 1 || c(&list[ix + 1], key) == Ordering::Greater {
+                if ix == list_len - 1 || cmp.is_gt(&list[ix + 1], key)? {
                     break;
                 } else {
                     lim -= 1;
                 }
-            },
+            }
         };
         lim /= 2;
     }
-    base
+    Ok(base)
 }
 
-
-fn gallop<T, C: Fn(&T, &T) -> Ordering>(key: &T, list: &[T], mode: Mode, c: C) -> (usize, usize) {
+fn gallop<T, C: Comparator<T>>(
+    key: &T,
+    list: &[T],
+    mode: Mode,
+    cmp: &C,
+) -> Result<(usize, usize), C::Error> {
     let list_len = list.len();
     if list_len == 0 {
-        return (0, 0);
+        return Ok((0, 0));
     }
-    match mode {
+    let ret = match mode {
         Mode::Forward => {
             let mut prev_val = 0;
             let mut next_val = 1;
             while next_val < list_len {
-                match c(&list[next_val], key) {
+                match cmp.ordering(&list[next_val], key)? {
                     Ordering::Less => {
                         prev_val = next_val;
                         next_val = ((next_val + 1) * 2) - 1;
-                    },
+                    }
                     Ordering::Greater => {
                         break;
-                    },
+                    }
                     Ordering::Equal => {
                         next_val += 1;
                         break;
-                    },
+                    }
                 }
             }
             if next_val > list_len {
                 next_val = list_len;
             }
             (prev_val, next_val - prev_val)
-        },
+        }
         Mode::Reverse => {
             let mut prev_val = list_len;
             let mut next_val = ((prev_val + 1) / 2) - 1;
-            loop {
-                match c(&list[next_val], key) {
-                    Ordering::Greater => {
-                        prev_val = next_val + 1;
-                        next_val = (next_val + 1) / 2;
-                        if next_val != 0 {
-                            next_val -= 1;
-                        } else {
-                            break;
-                        }
-                    },
-                    Ordering::Less | Ordering::Equal => {
-                        break;
-                    },
+            while cmp.is_gt(&list[next_val], key)? {
+                prev_val = next_val + 1;
+                next_val = (next_val + 1) / 2;
+                if next_val != 0 {
+                    next_val -= 1;
+                } else {
+                    break;
                 }
             }
             (next_val, prev_val - next_val)
         }
-    }
+    };
+    Ok(ret)
 }
diff --git a/src/gallop/tests.rs b/src/gallop/tests.rs
@@ -1,18 +1,19 @@
-use gallop::{self, Mode};
+use super::Mode;
+use crate::{never, ord_t_comparator};
 
 macro_rules! test_both {
     ($v:ident, $($x:expr);*) => {{
         let $v = Mode::Forward;
-        $($x;)*;
+        $($x;)*
         let $v = Mode::Reverse;
-        $($x;)*;
+        $($x;)*
     }}
 }
 
 #[test]
 fn gallop_empty() {
     let list: &[usize] = &[];
-    test_both!{mode,
+    test_both! {mode,
         assert_eq!(gallop_left(&0, list, mode), 0);
         assert_eq!(gallop_right(&0, list, mode), 0)
     }
@@ -21,7 +22,7 @@ fn gallop_empty() {
 #[test]
 fn gallop_single_greater() {
     let list: &[usize] = &[1];
-    test_both!{mode,
+    test_both! {mode,
         assert_eq!(gallop_left(&0, list, mode), 0);
         assert_eq!(gallop_right(&0, list, mode), 0)
     }
@@ -30,7 +31,7 @@ fn gallop_single_greater() {
 #[test]
 fn gallop_single_equal() {
     let list: &[usize] = &[1];
-    test_both!{mode,
+    test_both! {mode,
         assert_eq!(gallop_left(&1, list, mode), 0);
         assert_eq!(gallop_right(&1, list, mode), 1)
     }
@@ -39,7 +40,7 @@ fn gallop_single_equal() {
 #[test]
 fn gallop_single_less() {
     let list: &[usize] = &[1];
-    test_both!{mode,
+    test_both! {mode,
         assert_eq!(gallop_left(&2, list, mode), 1);
         assert_eq!(gallop_right(&2, list, mode), 1)
     }
@@ -48,7 +49,7 @@ fn gallop_single_less() {
 #[test]
 fn gallop_start_less() {
     let list: &[usize] = &[1, 2, 3];
-    test_both!{mode,
+    test_both! {mode,
         assert_eq!(gallop_left(&0, list, mode), 0);
         assert_eq!(gallop_right(&0, list, mode), 0)
     }
@@ -57,7 +58,7 @@ fn gallop_start_less() {
 #[test]
 fn gallop_start_equal() {
     let list: &[usize] = &[1, 2, 3];
-    test_both!{mode,
+    test_both! {mode,
         assert_eq!(gallop_left(&1, list, mode), 0);
         assert_eq!(gallop_right(&1, list, mode), 1)
     }
@@ -66,7 +67,7 @@ fn gallop_start_equal() {
 #[test]
 fn gallop_middle_equal() {
     let list: &[usize] = &[1, 2, 3];
-    test_both!{mode,
+    test_both! {mode,
         assert_eq!(gallop_left(&2, list, mode), 1);
         assert_eq!(gallop_right(&2, list, mode), 2)
     }
@@ -75,7 +76,7 @@ fn gallop_middle_equal() {
 #[test]
 fn gallop_end_equal() {
     let list: &[usize] = &[1, 2, 3];
-    test_both!{mode,
+    test_both! {mode,
         assert_eq!(gallop_left(&3, list, mode), 2);
         assert_eq!(gallop_right(&3, list, mode), 3)
     }
@@ -84,7 +85,7 @@ fn gallop_end_equal() {
 #[test]
 fn gallop_end_greater() {
     let list: &[usize] = &[1, 2, 3];
-    test_both!{mode,
+    test_both! {mode,
         assert_eq!(gallop_left(&4, list, mode), 3);
         assert_eq!(gallop_right(&4, list, mode), 3)
     }
@@ -93,7 +94,7 @@ fn gallop_end_greater() {
 #[test]
 fn gallop_end_middle_before() {
     let list: &[usize] = &[1, 3, 5];
-    test_both!{mode,
+    test_both! {mode,
         assert_eq!(gallop_left(&2, list, mode), 1);
         assert_eq!(gallop_right(&2, list, mode), 1)
     }
@@ -102,7 +103,7 @@ fn gallop_end_middle_before() {
 #[test]
 fn gallop_end_middle_after() {
     let list: &[usize] = &[1, 3, 5];
-    test_both!{mode,
+    test_both! {mode,
         assert_eq!(gallop_left(&4, list, mode), 2);
         assert_eq!(gallop_right(&4, list, mode), 2)
     }
@@ -111,7 +112,7 @@ fn gallop_end_middle_after() {
 #[test]
 fn gallop_large_start_before() {
     let list: &[usize] = &[1, 3, 5, 7, 11, 21, 31, 41, 51, 61, 71, 81, 91, 101];
-    test_both!{mode,
+    test_both! {mode,
         assert_eq!(gallop_left(&0, list, mode), 0);
         assert_eq!(gallop_right(&0, list, mode), 0)
     }
@@ -120,7 +121,7 @@ fn gallop_large_start_before() {
 #[test]
 fn gallop_large_start_equal() {
     let list: &[usize] = &[1, 3, 5, 7, 11, 21, 31, 41, 51, 61, 71, 81, 91, 101];
-    test_both!{mode,
+    test_both! {mode,
         assert_eq!(gallop_left(&1, list, mode), 0);
         assert_eq!(gallop_right(&1, list, mode), 1)
     }
@@ -129,7 +130,7 @@ fn gallop_large_start_equal() {
 #[test]
 fn gallop_large_start_after() {
     let list: &[usize] = &[1, 3, 5, 7, 11, 21, 31, 41, 51, 61, 71, 81, 91, 101];
-    test_both!{mode,
+    test_both! {mode,
         assert_eq!(gallop_left(&2, list, mode), 1);
         assert_eq!(gallop_right(&2, list, mode), 1)
     }
@@ -138,7 +139,7 @@ fn gallop_large_start_after() {
 #[test]
 fn gallop_large_center_equal() {
     let list: &[usize] = &[1, 3, 5, 7, 11, 21, 31, 41, 51, 61, 71, 81, 91, 101];
-    test_both!{mode,
+    test_both! {mode,
         assert_eq!(gallop_left(&21, list, mode), 5);
         assert_eq!(gallop_right(&21, list, mode), 6)
     }
@@ -147,7 +148,7 @@ fn gallop_large_center_equal() {
 #[test]
 fn gallop_large_center_less() {
     let list: &[usize] = &[1, 3, 5, 7, 11, 21, 31, 41, 51, 61, 71, 81, 91, 101];
-    test_both!{mode,
+    test_both! {mode,
         assert_eq!(gallop_left(&20, list, mode), 5);
         assert_eq!(gallop_right(&20, list, mode), 5)
     }
@@ -156,7 +157,7 @@ fn gallop_large_center_less() {
 #[test]
 fn gallop_large_end_less() {
     let list: &[usize] = &[1, 3, 5, 7, 11, 21, 31, 41, 51, 61, 71, 81, 91, 101];
-    test_both!{mode,
+    test_both! {mode,
         assert_eq!(gallop_left(&100, list, mode), 13);
         assert_eq!(gallop_right(&100, list, mode), 13)
     }
@@ -165,7 +166,7 @@ fn gallop_large_end_less() {
 #[test]
 fn gallop_large_end_equal() {
     let list: &[usize] = &[1, 3, 5, 7, 11, 21, 31, 41, 51, 61, 71, 81, 91, 101];
-    test_both!{mode,
+    test_both! {mode,
         assert_eq!(gallop_left(&101, list, mode), 13);
         assert_eq!(gallop_right(&101, list, mode), 14)
     }
@@ -174,17 +175,16 @@ fn gallop_large_end_equal() {
 #[test]
 fn gallop_large_end_greater() {
     let list: &[usize] = &[1, 3, 5, 7, 11, 21, 31, 41, 51, 61, 71, 81, 91, 101];
-    test_both!{mode,
+    test_both! {mode,
         assert_eq!(gallop_left(&102, list, mode), 14);
         assert_eq!(gallop_right(&102, list, mode), 14)
     }
 }
 
-pub fn gallop_left<T: Ord>(key: &T, list: &[T], mode: Mode) -> usize {
-    gallop::gallop_left(key, list, mode, |a, b| a.cmp(b) )
+fn gallop_left<T: Ord>(key: &T, list: &[T], mode: Mode) -> usize {
+    super::gallop_left(key, list, mode, &ord_t_comparator()).unwrap_or_else(never)
 }
 
-pub fn gallop_right<T: Ord>(key: &T, list: &[T], mode: Mode) -> usize {
-    gallop::gallop_right(key, list, mode, |a, b| a.cmp(b) )
+fn gallop_right<T: Ord>(key: &T, list: &[T], mode: Mode) -> usize {
+    super::gallop_right(key, list, mode, &ord_t_comparator()).unwrap_or_else(never)
 }
-
diff --git a/src/insort.rs b/src/insort.rs
@@ -0,0 +1,31 @@
+//! The bottom sorting algorithm (we could just have 1-element runs and do all
+//! the sorting with the merge algorithm, but that would be much slower).
+
+#[cfg(test)]
+mod tests;
+
+use crate::Comparator;
+
+/// Sorts the list using insertion sort.
+// This version was almost completely copied from libcollections/slice.rs
+pub(crate) fn sort<T, C: Comparator<T>>(list: &mut [T], cmp: &C) -> Result<(), C::Error> {
+    if list.len() < 2 {
+        return Ok(());
+    }
+    for i in 0..list.len() {
+        let i_el = &list[i];
+        // find the index just above the element that is in order wrt list[i]
+        let mut j = 0;
+        for (jj, j_el) in list[..i].iter().enumerate().rev() {
+            if !cmp.is_gt(j_el, i_el)? {
+                j = jj + 1;
+                break;
+            }
+        }
+        if i != j {
+            // SAFETY: j<i, i<list.len
+            unsafe { list.get_unchecked_mut(j..=i).rotate_right(1) };
+        }
+    }
+    Ok(())
+}
diff --git a/src/insort/mod.rs b/src/insort/mod.rs
diff --git a/src/insort/tests.rs b/src/insort/tests.rs
@@ -1,11 +1,11 @@
-use insort;
+use crate::{comparator, never, ord_t_comparator};
 
 /// Test the insertion sort implementation with an empty list
 #[test]
 fn empty() {
     let mut list: Vec<u32> = vec![];
     sort(&mut list);
-    assert!(list.len() == 0);
+    assert!(list.is_empty());
 }
 
 /// Test the insertion sort implementation with a single-element list
@@ -59,27 +59,26 @@ fn stable() {
     struct Item {
         key1: usize,
         key2: usize,
-    };
-    let mut list: Vec<Item> = (0..len).map(|_| {
-        key1 += 1;
-        key1 %= 5;
-        key2 += 1;
-        Item {
-            key1: key1,
-            key2: key2,
-        }
-    }).collect();
-    insort::sort(&mut list, |a, b| a.key1.cmp(&b.key1));
-    for i in (0 .. (len - 1)) {
-        assert!(list[i].key1 <= list[i + 1].key1);
-        if list[i].key1 == list[i + 1].key1 {
-            assert!(list[i].key2 <= list[i + 1].key2);
+    }
+    let mut list: Vec<Item> = (0..len)
+        .map(|_| {
+            key1 += 1;
+            key1 %= 5;
+            key2 += 1;
+            Item { key1, key2 }
+        })
+        .collect();
+    super::sort(&mut list, &comparator(|a: &Item, b| Ok(a.key1 > b.key1))).unwrap_or_else(never);
+    for pair in list.windows(2) {
+        let (a, b) = (&pair[0], &pair[1]);
+        assert!(a.key1 <= b.key1);
+        if a.key1 == b.key1 {
+            assert!(a.key2 <= b.key2);
         }
     }
 }
 
 /// Insertion sort implementation convenience used for tests.
-pub fn sort<T: Ord>(list: &mut[T]) {
-    insort::sort(list, |a, b| a.cmp(b) );
+fn sort<T: Ord>(list: &mut [T]) {
+    super::sort(list, &ord_t_comparator()).unwrap_or_else(never);
 }
-
diff --git a/src/lib.rs b/src/lib.rs
@@ -3,17 +3,106 @@
 //! on an already-sorted list, smoothly becoming O(n log n) as the sorted
 //! sections (runs) get smaller and smaller.
 
+#![cfg_attr(not(test), no_std)]
+
+extern crate alloc;
+
+mod find_run;
+mod gallop;
 mod insort;
 mod merge;
-mod gallop;
-mod find_run;
 mod sort;
 
-pub use sort::sort as sort_by;
+use core::cmp::Ordering;
+use core::convert::Infallible;
+use sort::try_sort_by as try_sort_by_cmp;
+
+type NeverResult<T> = Result<T, Infallible>;
+#[inline(always)]
+fn never<T>(x: Infallible) -> T {
+    match x {}
+}
+
+pub fn try_sort_by_gt<T, E, C: Fn(&T, &T) -> Result<bool, E>>(
+    list: &mut [T],
+    cmp: C,
+) -> Result<(), E> {
+    try_sort_by_cmp(list, cmp)
+}
+
+#[inline]
+pub fn try_sort_by<T, E, C: Fn(&T, &T) -> Result<Ordering, E>>(
+    list: &mut [T],
+    cmp: C,
+) -> Result<(), E> {
+    try_sort_by_cmp(list, ord_comparator(cmp))
+}
+
+#[inline]
+pub fn sort_by_gt<T, C: Fn(&T, &T) -> bool>(list: &mut [T], is_greater: C) {
+    try_sort_by_gt(list, move |a, b| -> NeverResult<_> { Ok(is_greater(a, b)) })
+        .unwrap_or_else(never)
+}
+
+#[inline]
+pub fn sort_by<T, C: Fn(&T, &T) -> Ordering>(list: &mut [T], cmp: C) {
+    try_sort_by(list, move |a, b| -> NeverResult<_> { Ok(cmp(a, b)) }).unwrap_or_else(never)
+}
+
+#[inline]
+pub fn sort<T: Ord>(list: &mut [T]) {
+    sort_by(list, Ord::cmp)
+}
+
+trait Comparator<T> {
+    type Error;
+    fn is_gt(&self, lhs: &T, rhs: &T) -> Result<bool, Self::Error>;
+    fn ordering(&self, lhs: &T, rhs: &T) -> Result<Ordering, Self::Error> {
+        let ord = if self.is_gt(lhs, rhs)? {
+            Ordering::Greater
+        } else if self.is_gt(rhs, lhs)? {
+            Ordering::Less
+        } else {
+            Ordering::Equal
+        };
+        Ok(ord)
+    }
+}
+
+impl<F, T, E> Comparator<T> for F
+where
+    F: Fn(&T, &T) -> Result<bool, E>,
+{
+    type Error = E;
+    fn is_gt(&self, lhs: &T, rhs: &T) -> Result<bool, E> {
+        self(lhs, rhs)
+    }
+}
+
+// really weird, idk why this is necessary...
+#[cfg(test)]
+pub(crate) fn comparator<T>(
+    f: impl Fn(&T, &T) -> NeverResult<bool>,
+) -> impl Comparator<T, Error = Infallible> {
+    f
+}
+#[cfg(test)]
+pub(crate) fn ord_t_comparator<T: Ord>() -> impl Comparator<T, Error = Infallible> {
+    ord_comparator(|a: &T, b| Ok(a.cmp(b)))
+}
 
-use std::cmp::Ordering;
-pub fn sort<T: PartialOrd>(list: &mut [T]) {
-    sort_by(list, |a, b| {
-        a.partial_cmp(b).unwrap_or(Ordering::Equal)
-    })
+pub(crate) fn ord_comparator<T, E, F: Fn(&T, &T) -> Result<Ordering, E>>(
+    f: F,
+) -> impl Comparator<T, Error = E> {
+    struct OrdComparator<F>(F);
+    impl<T, E, F: Fn(&T, &T) -> Result<Ordering, E>> Comparator<T> for OrdComparator<F> {
+        type Error = E;
+        fn is_gt(&self, lhs: &T, rhs: &T) -> Result<bool, E> {
+            (self.0)(lhs, rhs).map(|ord| ord == Ordering::Greater)
+        }
+        fn ordering(&self, lhs: &T, rhs: &T) -> Result<Ordering, Self::Error> {
+            (self.0)(lhs, rhs)
+        }
+    }
+    OrdComparator(f)
 }
diff --git a/src/merge.rs b/src/merge.rs
@@ -0,0 +1,353 @@
+//! The merge algorithm. This one can merge unequal slices, allocating an n/2
+//! sized temporary slice of the same type. Naturally, it can only merge slices
+//! that are themselves already sorted.
+
+#[cfg(test)]
+mod tests;
+
+use crate::gallop::{self, gallop_left, gallop_right};
+use crate::Comparator;
+use alloc::vec::Vec;
+use core::mem::ManuallyDrop;
+use core::ptr;
+
+/// Merge implementation switch.
+pub(crate) fn merge<T, C: Comparator<T>>(
+    list: &mut [T],
+    mut first_len: usize,
+    cmp: &C,
+) -> Result<(), C::Error> {
+    if first_len == 0 {
+        return Ok(());
+    }
+    let (first, second) = list.split_at_mut(first_len);
+    let second_len = gallop_left(first.last().unwrap(), second, gallop::Mode::Reverse, cmp)?;
+    let first_of_second = match second.get(0) {
+        Some(x) => x,
+        None => return Ok(()),
+    };
+    let first_off = gallop_right(first_of_second, first, gallop::Mode::Forward, cmp)?;
+    first_len -= first_off;
+    if first_len == 0 {
+        return Ok(());
+    }
+
+    let nlist = &mut list[first_off..][..first_len + second_len];
+    if first_len > second_len {
+        merge_hi(nlist, first_len, second_len, cmp)
+    } else {
+        merge_lo(nlist, first_len, cmp)
+    }
+}
+
+/// The number of times any one run can win before we try galloping.
+/// Change this during testing.
+const MIN_GALLOP: usize = 7;
+
+/// Merge implementation used when the first run is smaller than the second.
+pub(crate) fn merge_lo<T, C: Comparator<T>>(
+    list: &mut [T],
+    first_len: usize,
+    cmp: &C,
+) -> Result<(), C::Error> {
+    MergeLo::new(list, first_len, cmp).merge()
+}
+
+#[inline(always)]
+fn md_as_inner<T>(x: &[ManuallyDrop<T>]) -> &[T] {
+    // SAFETY: ManuallyDrop<T> is repr(transparent) over T
+    unsafe { &*(x as *const [_] as *const [T]) }
+}
+
+/// Implementation of `merge_lo`. We need to have an object in order to
+/// implement panic safety.
+struct MergeLo<'a, T, C: Comparator<T>> {
+    list_len: usize,
+    first_pos: usize,
+    first_len: usize,
+    second_pos: usize,
+    dest_pos: usize,
+    list: &'a mut [T],
+    tmp: Vec<ManuallyDrop<T>>,
+    cmp: &'a C,
+}
+impl<'a, T, C: Comparator<T>> MergeLo<'a, T, C> {
+    /// Constructor for a lower merge.
+    fn new(list: &'a mut [T], first_len: usize, cmp: &'a C) -> Self {
+        let mut ret_val = MergeLo {
+            list_len: list.len(),
+            first_pos: 0,
+            first_len,
+            second_pos: first_len,
+            dest_pos: 0,
+            list,
+            tmp: Vec::with_capacity(first_len),
+            cmp,
+        };
+        // First, move the smallest run into temporary storage, leaving the
+        // original contents uninitialized.
+        unsafe {
+            ret_val.tmp.set_len(first_len);
+            ptr::copy_nonoverlapping(
+                ret_val.list.as_ptr() as *const ManuallyDrop<T>,
+                ret_val.tmp.as_mut_ptr(),
+                first_len,
+            );
+        }
+        ret_val
+    }
+    /// Perform the one-by-one comparison and insertion.
+    fn merge(mut self) -> Result<(), C::Error> {
+        let cmp = self.cmp;
+        let mut first_count = 0;
+        let mut second_count = 0;
+        while self.second_pos > self.dest_pos && self.second_pos < self.list_len {
+            debug_assert!(self.first_pos + (self.second_pos - self.first_len) == self.dest_pos);
+            if (second_count | first_count) < MIN_GALLOP {
+                // One-at-a-time mode.
+                unsafe {
+                    if cmp.is_gt(
+                        self.tmp.get_unchecked(self.first_pos),
+                        self.list.get_unchecked(self.second_pos),
+                    )? {
+                        ptr::copy_nonoverlapping(
+                            self.list.get_unchecked(self.second_pos),
+                            self.list.get_unchecked_mut(self.dest_pos),
+                            1,
+                        );
+                        self.second_pos += 1;
+                        second_count += 1;
+                        first_count = 0;
+                    } else {
+                        ptr::copy_nonoverlapping(
+                            &**self.tmp.get_unchecked(self.first_pos),
+                            self.list.get_unchecked_mut(self.dest_pos),
+                            1,
+                        );
+                        self.first_pos += 1;
+                        first_count += 1;
+                        second_count = 0;
+                    }
+                }
+                self.dest_pos += 1;
+            } else {
+                // Galloping mode.
+                second_count = gallop_left(
+                    unsafe { md_as_inner(&self.tmp).get_unchecked(self.first_pos) },
+                    &self.list[self.second_pos..],
+                    gallop::Mode::Forward,
+                    cmp,
+                )?;
+                unsafe {
+                    ptr::copy(
+                        self.list.get_unchecked(self.second_pos),
+                        self.list.get_unchecked_mut(self.dest_pos),
+                        second_count,
+                    )
+                }
+                self.dest_pos += second_count;
+                self.second_pos += second_count;
+                debug_assert!(self.first_pos + (self.second_pos - self.first_len) == self.dest_pos);
+                if self.second_pos > self.dest_pos && self.second_pos < self.list_len {
+                    first_count = gallop_right(
+                        unsafe { self.list.get_unchecked(self.second_pos) },
+                        md_as_inner(&self.tmp[self.first_pos..]),
+                        gallop::Mode::Forward,
+                        cmp,
+                    )?;
+                    unsafe {
+                        ptr::copy_nonoverlapping(
+                            md_as_inner(&self.tmp).get_unchecked(self.first_pos),
+                            self.list.get_unchecked_mut(self.dest_pos),
+                            first_count,
+                        )
+                    };
+                    self.dest_pos += first_count;
+                    self.first_pos += first_count;
+                }
+            }
+        }
+        Ok(())
+    }
+}
+impl<'a, T, C: Comparator<T>> Drop for MergeLo<'a, T, C> {
+    /// Copy all remaining items in the temporary storage into the list.
+    /// If the comparator panics, the result will not be sorted, but will still
+    /// contain no duplicates or uninitialized spots.
+    fn drop(&mut self) {
+        unsafe {
+            // Make sure that the entire tmp storage is consumed. Since there are no uninitialized
+            // spaces before dest_pos, and no uninitialized space after first_pos, this will ensure
+            // that there are no uninitialized spaces inside the slice after we drop. Thus, the
+            // function is safe.
+            if self.first_pos < self.first_len {
+                ptr::copy_nonoverlapping(
+                    self.tmp.get_unchecked(self.first_pos) as *const _ as *const T,
+                    self.list.get_unchecked_mut(self.dest_pos),
+                    self.first_len - self.first_pos,
+                );
+            }
+            // The temporary storage is now full of nothing but uninitialized.
+            // We want to deallocate the space, but not call the destructors.
+            self.tmp.set_len(0);
+        }
+    }
+}
+
+/// Merge implementation used when the first run is larger than the second.
+pub(crate) fn merge_hi<T, C: Comparator<T>>(
+    list: &mut [T],
+    first_len: usize,
+    second_len: usize,
+    cmp: &C,
+) -> Result<(), C::Error> {
+    MergeHi::new(list, first_len, second_len, cmp).merge()
+}
+
+/// Implementation of `merge_hi`. We need to have an object in order to
+/// implement panic safety.
+struct MergeHi<'a, T, C: Comparator<T>> {
+    first_pos: isize,
+    second_pos: isize,
+    dest_pos: isize,
+    list: &'a mut [T],
+    tmp: Vec<ManuallyDrop<T>>,
+    cmp: &'a C,
+}
+
+impl<'a, T, C: Comparator<T>> MergeHi<'a, T, C> {
+    /// Constructor for a higher merge.
+    fn new(list: &'a mut [T], first_len: usize, second_len: usize, cmp: &'a C) -> Self {
+        let mut ret_val = MergeHi {
+            first_pos: first_len as isize - 1,
+            second_pos: second_len as isize - 1,
+            dest_pos: list.len() as isize - 1,
+            list,
+            tmp: Vec::with_capacity(second_len),
+            cmp,
+        };
+        // First, move the smallest run into temporary storage, leaving the
+        // original contents uninitialized.
+        unsafe {
+            ret_val.tmp.set_len(second_len);
+            ptr::copy_nonoverlapping(
+                ret_val.list.as_ptr().add(first_len),
+                ret_val.tmp.as_mut_ptr() as *mut T,
+                second_len,
+            );
+        }
+        ret_val
+    }
+    /// Perform the one-by-one comparison and insertion.
+    fn merge(mut self) -> Result<(), C::Error> {
+        let cmp = self.cmp;
+        let mut first_count: usize = 0;
+        let mut second_count: usize = 0;
+        while self.first_pos < self.dest_pos && self.first_pos >= 0 {
+            debug_assert!(self.first_pos + self.second_pos + 1 == self.dest_pos);
+            if (second_count | first_count) < MIN_GALLOP {
+                // One-at-a-time mode.
+                unsafe {
+                    if cmp.is_gt(
+                        self.list.get_unchecked(self.first_pos as usize),
+                        self.tmp.get_unchecked(self.second_pos as usize),
+                    )? {
+                        ptr::copy_nonoverlapping(
+                            self.list.get_unchecked(self.first_pos as usize),
+                            self.list.get_unchecked_mut(self.dest_pos as usize),
+                            1,
+                        );
+                        self.first_pos -= 1;
+                    } else {
+                        ptr::copy_nonoverlapping(
+                            md_as_inner(&self.tmp).get_unchecked(self.second_pos as usize),
+                            self.list.get_unchecked_mut(self.dest_pos as usize),
+                            1,
+                        );
+                        self.second_pos -= 1;
+                    }
+                }
+                self.dest_pos -= 1;
+            } else {
+                // Galloping mode.
+                first_count = self.first_pos as usize + 1
+                    - gallop_right(
+                        unsafe { md_as_inner(&self.tmp).get_unchecked(self.second_pos as usize) },
+                        &self.list[..=self.first_pos as usize],
+                        gallop::Mode::Reverse,
+                        cmp,
+                    )?;
+                unsafe {
+                    copy_backwards(
+                        self.list.get_unchecked(self.first_pos as usize),
+                        self.list.get_unchecked_mut(self.dest_pos as usize),
+                        first_count,
+                    )
+                }
+                self.dest_pos -= first_count as isize;
+                self.first_pos -= first_count as isize;
+                debug_assert!(self.first_pos + self.second_pos + 1 == self.dest_pos);
+                if self.first_pos < self.dest_pos && self.first_pos >= 0 {
+                    second_count = self.second_pos as usize + 1
+                        - gallop_left(
+                            unsafe { self.list.get_unchecked(self.first_pos as usize) },
+                            md_as_inner(&self.tmp[..=self.second_pos as usize]),
+                            gallop::Mode::Reverse,
+                            cmp,
+                        )?;
+                    unsafe {
+                        copy_nonoverlapping_backwards(
+                            md_as_inner(&self.tmp).get_unchecked(self.second_pos as usize),
+                            self.list.get_unchecked_mut(self.dest_pos as usize),
+                            second_count,
+                        )
+                    }
+                    self.dest_pos -= second_count as isize;
+                    self.second_pos -= second_count as isize;
+                }
+            }
+        }
+        Ok(())
+    }
+}
+
+/// Perform a backwards `ptr::copy_nonoverlapping`. Behave identically when size = 1, but behave
+/// differently all other times
+unsafe fn copy_backwards<T>(src: *const T, dest: *mut T, size: usize) {
+    ptr::copy(
+        src.sub(size.wrapping_sub(1)),
+        dest.sub(size.wrapping_sub(1)),
+        size,
+    )
+}
+
+/// Perform a backwards `ptr::copy_nonoverlapping`. Behave identically when size = 1, but behave
+/// differently all other times
+unsafe fn copy_nonoverlapping_backwards<T>(src: *const T, dest: *mut T, size: usize) {
+    ptr::copy_nonoverlapping(
+        src.sub(size.wrapping_sub(1)),
+        dest.sub(size.wrapping_sub(1)),
+        size,
+    )
+}
+
+impl<'a, T, C: Comparator<T>> Drop for MergeHi<'a, T, C> {
+    /// Copy all remaining items in the temporary storage into the list.
+    /// If the comparator panics, the result will not be sorted, but will still
+    /// contain no duplicates or uninitialized spots.
+    fn drop(&mut self) {
+        unsafe {
+            // Make sure that the entire tmp storage is consumed. Since there are no uninitialized
+            // spaces before dest_pos, and no uninitialized space after first_pos, this will ensure
+            // that there are no uninitialized spaces inside the slice after we drop. Thus, the
+            // function is safe.
+            if self.second_pos >= 0 {
+                copy_nonoverlapping_backwards(
+                    md_as_inner(&self.tmp).get_unchecked(self.second_pos as usize),
+                    self.list.get_unchecked_mut(self.dest_pos as usize),
+                    self.second_pos as usize + 1,
+                );
+            }
+        }
+    }
+}
diff --git a/src/merge/mod.rs b/src/merge/mod.rs
diff --git a/src/merge/tests.rs b/src/merge/tests.rs
@@ -2,14 +2,14 @@
 //! sized temporary slice of the same type. Naturally, it can only merge slices
 //! that are themselves already sorted.
 
-use merge;
+use crate::{comparator, never, ord_t_comparator};
 
 /// Test mergeing two empty slices.
 #[test]
 fn empty() {
     let mut list: Vec<u32> = vec![];
     merge(&mut list, 0);
-    assert!(list.len() == 0);
+    assert!(list.is_empty());
 }
 
 /// Test merging two equal-sized single-element vectors that are already sorted.
@@ -81,15 +81,21 @@ fn lo_unsorted_multiple() {
 /// Test panic safety when the first run is longest
 #[test]
 fn lo_panic() {
-    use std::thread;
-    let mut list = vec![1, 2, 3, 4, 5];
-    unsafe {
-        let list2p: *mut Vec<usize> = &mut list;
-        let list2: &mut Vec<usize> = &mut *list2p;
-        let _ = thread::spawn(move || {
-            merge::merge(list2, 3, |_, _| { panic!("Expected panic: this is normal") });
-        }).join().err().unwrap();
-    }
+    use std::panic::{catch_unwind, AssertUnwindSafe};
+
+    let mut list = vec![1usize, 2, 3, 4, 5];
+
+    catch_unwind(AssertUnwindSafe(|| {
+        super::merge(
+            &mut list,
+            3,
+            &comparator(|_, _| panic!("Expected panic: this is normal")),
+        )
+        .unwrap_or_else(never)
+    }))
+    .err()
+    .unwrap();
+
     assert!(list[0] == 1);
     assert!(list[1] == 2);
     assert!(list[2] == 3);
@@ -100,15 +106,21 @@ fn lo_panic() {
 /// Test panic safety when the second run is longest
 #[test]
 fn hi_panic() {
-    use std::thread;
-    let mut list = vec![1, 2, 3, 4, 5];
-    unsafe {
-        let list2p: *mut Vec<usize> = &mut list;
-        let list2: &mut Vec<usize> = &mut *list2p;
-        let _ = thread::spawn(move || {
-            merge::merge(list2, 2, |_, _| { panic!("Expected panic: this is normal") });
-        }).join().err().unwrap();
-    }
+    use std::panic::{catch_unwind, AssertUnwindSafe};
+
+    let mut list = vec![1usize, 2, 3, 4, 5];
+
+    catch_unwind(AssertUnwindSafe(|| {
+        super::merge(
+            &mut list,
+            2,
+            &comparator(|_, _| panic!("Expected panic: this is normal")),
+        )
+        .unwrap_or_else(never)
+    }))
+    .err()
+    .unwrap();
+
     assert!(list[0] == 1);
     assert!(list[1] == 2);
     assert!(list[2] == 3);
@@ -118,45 +130,42 @@ fn hi_panic() {
 
 /// Test that the drop() is never run while sorting.
 
+#[derive(Debug, PartialOrd, Ord, PartialEq, Eq)]
+struct ExplodeOnDrop(usize);
+impl Drop for ExplodeOnDrop {
+    fn drop(&mut self) {
+        panic!("We're not supposed to panic.");
+    }
+}
+
 #[test]
 fn lo_nodrop() {
-    #[derive(Debug)]
-    struct ExplodeOnDrop(usize);
-    impl Drop for ExplodeOnDrop {
-        fn drop(&mut self) {
-           // panic!("We're not supposed to panic.");
-        }
-    }
     let mut list = vec![ExplodeOnDrop(3), ExplodeOnDrop(7), ExplodeOnDrop(2)];
-    merge::merge(&mut list, 2, |a, b| {a.0.cmp(&b.0) });
+    merge(&mut list, 2);
     assert!(list[0].0 == 2);
     assert!(list[1].0 == 3);
     assert!(list[2].0 == 7);
-    unsafe { list.set_len(0); }
+    list.into_iter().for_each(std::mem::forget);
 }
 
 #[test]
 fn hi_nodrop() {
-    #[derive(Debug)]
-    struct ExplodeOnDrop(usize);
-    impl Drop for ExplodeOnDrop {
-        fn drop(&mut self) {
-            panic!("We're not supposed to panic.");
-        }
-    }
     let mut list = vec![ExplodeOnDrop(3), ExplodeOnDrop(2), ExplodeOnDrop(7)];
-    merge::merge(&mut list, 1, |a, b| {a.0.cmp(&b.0) });
+    merge(&mut list, 1);
     assert!(list[0].0 == 2);
     assert!(list[1].0 == 3);
     assert!(list[2].0 == 7);
-    unsafe { list.set_len(0); }
+    list.into_iter().for_each(std::mem::forget);
 }
 
 /// Ensure that, when we enter galloping mode, we still work right.
 
 #[test]
 fn lo_gallop_stress() {
-    let mut list = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20];
+    let mut list = vec![
+        1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 11, 12, 13, 14,
+        15, 16, 17, 18, 19, 20,
+    ];
     merge(&mut list, 21);
     assert!(list[0] == 1);
     assert!(list[1] == 2);
@@ -195,7 +204,10 @@ fn lo_gallop_stress() {
 
 #[test]
 fn hi_gallop_stress() {
-    let mut list = vec![11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30];
+    let mut list = vec![
+        11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 22, 23, 24,
+        25, 26, 27, 28, 29, 30,
+    ];
     merge(&mut list, 10);
     assert!(list[0] == 1);
     assert!(list[1] == 2);
@@ -231,7 +243,6 @@ fn hi_gallop_stress() {
 }
 
 /// Merge convenience used for tests.
-pub fn merge<T: Ord>(list: &mut [T], first_len: usize) {
-    merge::merge(list, first_len, |a, b| a.cmp(b) );
+fn merge<T: Ord>(list: &mut [T], first_len: usize) {
+    super::merge(list, first_len, &ord_t_comparator()).unwrap_or_else(never)
 }
-
diff --git a/src/sort/mod.rs → src/sort.rs b/src/sort/mod.rs → src/sort.rs
@@ -4,11 +4,12 @@
 #[cfg(test)]
 mod tests;
 
-use std::cmp::Ordering;
-use std::cmp::min;
-use find_run::get_run;
-use insort;
-use merge::merge;
+use crate::find_run::get_run;
+use crate::insort;
+use crate::merge::merge;
+use crate::Comparator;
+use alloc::vec::Vec;
+use core::cmp::min;
 
 /// Minimum run length to merge; anything shorter will be lengthend and
 /// sorted using `insort::sort`.
@@ -32,16 +33,16 @@ fn calc_min_merge(mut len: usize) -> usize {
 #[derive(Copy, Clone, Debug)]
 struct Run {
     pos: usize,
-    len: usize
+    len: usize,
 }
 
 /// All the ongoing state of the sort.
-struct SortState<'a, T: 'a, C: Fn(&T, &T) -> Ordering> {
+struct SortState<'a, T, C: Comparator<T>> {
     /// The list that is being sorted.
     list: &'a mut [T],
-    /// The comparator function. Should return `Ordering::Greater` if the first
-    /// argument is goes after the second.
-    c: C,
+    /// The comparator function. Should return true if the first argument is
+    /// greater than the second.
+    cmp: &'a C,
     /// The list of known-sorted sections of the list that can be merged.
     /// To keep the size of this list down, this invariant is preserved:
     ///  - `runs.len < 3 || runs[i-2].len > runs[i-1].len + runs[i].len`
@@ -52,104 +53,99 @@ struct SortState<'a, T: 'a, C: Fn(&T, &T) -> Ordering> {
     pos: usize,
 }
 
-impl<'a, T: 'a, C: Fn(&T, &T) -> Ordering> SortState<'a, T, C> {
-
-    fn new(list: &'a mut [T], c: C) -> SortState<'a, T, C> {
+impl<'a, T, C: Comparator<T>> SortState<'a, T, C> {
+    #[inline]
+    fn new(list: &'a mut [T], cmp: &'a C) -> SortState<'a, T, C> {
         SortState {
-            list: list,
-            c: c,
+            list,
+            cmp,
             runs: Vec::new(),
             pos: 0,
         }
     }
 
     /// The outer loop. Find runs, and move forward.
-    fn sort(&mut self) {
+    fn sort(&mut self) -> Result<(), C::Error> {
         let list_len = self.list.len();
         // Minimum run size to use merge sort on. Any sorted sections of the
         // list that are shorter than this are lengthened using `insort::sort`.
         let min_run = calc_min_merge(list_len);
         while self.pos < list_len {
             let pos = self.pos;
-            let mut run_len = get_run(self.list.split_at_mut(pos).1, &self.c);
+            let mut run_len = get_run(&mut self.list[pos..], self.cmp)?;
             let run_min_len = min(min_run, list_len - pos);
             if run_len < run_min_len {
                 run_len = run_min_len;
-                let l = self.list.split_at_mut(pos).1.split_at_mut(run_len).0;
-                insort::sort(l, &self.c);
+                let l = &mut self.list[pos..][..run_len];
+                insort::sort(l, self.cmp)?;
             }
-            self.runs.push(Run{
-                pos: pos,
-                len: run_len,
-            });
+            self.runs.push(Run { pos, len: run_len });
             self.pos += run_len;
-            self.merge_collapse();
+            self.merge_collapse()?;
         }
-        self.merge_force_collapse();
+        self.merge_force_collapse()?;
+        Ok(())
     }
 
     /// Merge the runs if they're too big.
     /// Copied almost verbatim from
     /// http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/#sec3.2
-    fn merge_collapse(&mut self) {
+    fn merge_collapse(&mut self) -> Result<(), C::Error> {
         let runs = &mut self.runs;
         while runs.len() > 1 {
-            let n = runs.len() - 2;
-            if    (n >= 1 && runs[n - 1].len <= runs[n].len + runs[n + 1].len)
-               || (n >= 2 && runs[n - 2].len <= runs[n].len + runs[n - 1].len) {
-                let (pos1, pos2) = if runs[n - 1].len < runs[n + 1].len {
-                    (n - 1, n)
+            let l = runs.len();
+            if (l >= 3 && runs[l - 1].len <= runs[l - 2].len + runs[l - 1].len)
+                || (l >= 4 && runs[l - 4].len <= runs[l - 2].len + runs[l - 3].len)
+            {
+                let (pos1, pos2) = if runs[l - 3].len < runs[l - 1].len {
+                    (l - 3, l - 2)
                 } else {
-                    (n, n + 1)
+                    (l - 2, l - 1)
                 };
                 let (run1, run2) = (runs[pos1], runs[pos2]);
                 debug_assert_eq!(run1.pos + run1.len, run2.pos);
                 runs.remove(pos2);
-                runs[pos1] = Run{
+                runs[pos1] = Run {
                     pos: run1.pos,
                     len: run1.len + run2.len,
                 };
-                let l = self.list.split_at_mut(run1.pos).1;
-                let l = l.split_at_mut(run1.len + run2.len).0;
-                merge(l, run1.len, &self.c);
+                let l = &mut self.list[run1.pos..][..run1.len + run2.len];
+                merge(l, run1.len, self.cmp)?;
             } else {
                 break; // Invariant established.
             }
         }
+        Ok(())
     }
 
     /// Merge any outstanding runs, at the end.
-    fn merge_force_collapse(&mut self) {
+    fn merge_force_collapse(&mut self) -> Result<(), C::Error> {
         let runs = &mut self.runs;
         while runs.len() > 1 {
-            let n = runs.len() - 2;
-            let (pos1, pos2) = if n > 0 && runs[n - 1].len < runs[n + 1].len {
-                (n - 1, n)
-            } else {
-                (n, n + 1)
-            };
+            let (mut pos1, mut pos2) = (runs.len() - 2, runs.len() - 1);
+            if runs.len() > 2 && runs[runs.len() - 3].len < runs[runs.len() - 1].len {
+                pos1 -= 1;
+                pos2 -= 1;
+            }
             let (run1, run2) = (runs[pos1], runs[pos2]);
             debug_assert_eq!(run1.len, run2.pos);
             runs.remove(pos2);
-            runs[pos1] = Run{
+            runs[pos1] = Run {
                 pos: run1.pos,
                 len: run1.len + run2.len,
             };
-            let l = self.list.split_at_mut(run1.pos).1;
-            let l = l.split_at_mut(run1.len + run2.len).0;
-            merge(l, run1.len, &self.c);
+            let l = &mut self.list[run1.pos..][..run1.len + run2.len];
+            merge(l, run1.len, self.cmp)?;
         }
+        Ok(())
     }
 }
 
 /// Sorts the list using merge sort.
-///
-/// `c(a, b)` should return std::cmp::Ordering::Greater when `a` is greater than `b`.
-pub fn sort<T, C: Fn(&T, &T) -> Ordering>(list: &mut [T], c: C) {
+pub(crate) fn try_sort_by<T, C: Comparator<T>>(list: &mut [T], cmp: C) -> Result<(), C::Error> {
     if list.len() < MIN_MERGE {
-        insort::sort(list, c);
+        insort::sort(list, &cmp)
     } else {
-        let mut sort_state = SortState::new(list, c);
-        sort_state.sort();
+        SortState::new(list, &cmp).sort()
     }
 }
diff --git a/src/sort/tests.rs b/src/sort/tests.rs
@@ -1,14 +1,14 @@
 //! The top sorting algorithm; that is, the modified merge sort we keep
 //! talking about.
 
-use sort as timsort;
+use crate::{never, ord_t_comparator};
 
 /// Test the sort implementation with an empty list
 #[test]
 fn empty() {
     let mut list: Vec<u32> = vec![];
     sort(&mut list);
-    assert!(list.len() == 0);
+    assert!(list.is_empty());
 }
 
 /// Test the sort implementation with a single-element list
@@ -62,18 +62,17 @@ fn stable_npow2() {
     struct Item {
         key1: usize,
         key2: usize,
-    };
-    let mut list: Vec<Item> = (0..len).map(|_| {
-        key1 += 1;
-        key1 %= 5;
-        key2 += 1;
-        Item {
-            key1: key1,
-            key2: key2,
-        }
-    }).collect();
-    timsort::sort(&mut list, |a, b| a.key1.cmp(&b.key1));
-    for i in (0 .. (len - 1)) {
+    }
+    let mut list: Vec<Item> = (0..len)
+        .map(|_| {
+            key1 += 1;
+            key1 %= 5;
+            key2 += 1;
+            Item { key1, key2 }
+        })
+        .collect();
+    crate::sort_by_gt(&mut list, |a, b| a.key1 > b.key1);
+    for i in 0..(len - 1) {
         assert!(list[i].key1 <= list[i + 1].key1);
         if list[i].key1 == list[i + 1].key1 {
             assert!(list[i].key2 <= list[i + 1].key2);
@@ -90,18 +89,17 @@ fn stable() {
     struct Item {
         key1: usize,
         key2: usize,
-    };
-    let mut list: Vec<Item> = (0..len).map(|_| {
-        key1 += 1;
-        key1 %= 5;
-        key2 += 1;
-        Item {
-            key1: key1,
-            key2: key2,
-        }
-    }).collect();
-    timsort::sort(&mut list, |a, b| a.key1.cmp(&b.key1));
-    for i in (0 .. (len - 1)) {
+    }
+    let mut list: Vec<Item> = (0..len)
+        .map(|_| {
+            key1 += 1;
+            key1 %= 5;
+            key2 += 1;
+            Item { key1, key2 }
+        })
+        .collect();
+    crate::sort_by_gt(&mut list, |a, b| a.key1 > b.key1);
+    for i in 0..(len - 1) {
         assert!(list[i].key1 <= list[i + 1].key1);
         if list[i].key1 == list[i + 1].key1 {
             assert!(list[i].key2 <= list[i + 1].key2);
@@ -110,8 +108,8 @@ fn stable() {
 }
 
 /// Sort implementation convenience used for tests.
-pub fn sort<T: Ord>(list: &mut[T]) {
-    let mut sort_state = timsort::SortState::new(list, |a, b| a.cmp(b) );
-    sort_state.sort();
+fn sort<T: Ord>(list: &mut [T]) {
+    super::SortState::new(list, &ord_t_comparator())
+        .sort()
+        .unwrap_or_else(never)
 }
-