From 89e82439186c6dfa48a73bddc0908a494fbd4394 Mon Sep 17 00:00:00 2001
From: JSDurand <mmemmew@gmail.com>
Date: Sat, 11 Mar 2023 16:21:20 +0800
Subject: optimize the implementation

Now the double for loop is eliminated and the time complexity is
indeed O(n log(n)).

Also added (micro)-benchmarks to roughly confirm the time complexity
is as predicted.
---
 benches/bench_sm.rs | 103 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 103 insertions(+)
 create mode 100644 benches/bench_sm.rs

(limited to 'benches')

diff --git a/benches/bench_sm.rs b/benches/bench_sm.rs
new file mode 100644
index 0000000..736397a
--- /dev/null
+++ b/benches/bench_sm.rs
@@ -0,0 +1,103 @@
+//! This file benchmarks the `sm` function.
+
+use criterion::{black_box, criterion_group, criterion_main, Criterion};
+
+use rand::{
+    distributions::{Distribution, Uniform},
+    thread_rng,
+};
+
+use sort::sm;
+
+fn bench_10(c: &mut Criterion) {
+    let mut rng = thread_rng();
+
+    let input = {
+        let uniform = Uniform::new(-100.0f32, 100.0f32);
+        uniform.sample_iter(&mut rng).take(10).collect::<Vec<_>>()
+    };
+
+    assert_eq!(input.len(), 10);
+
+    c.bench_function("sm", |b| {
+        b.iter(|| {
+            let mut count = 0;
+            black_box(sm(input.as_slice(), &mut count))
+        })
+    });
+}
+
+fn bench_20(c: &mut Criterion) {
+    let mut rng = thread_rng();
+
+    let input = {
+        let uniform = Uniform::new(-100.0f32, 100.0f32);
+        uniform.sample_iter(&mut rng).take(20).collect::<Vec<_>>()
+    };
+
+    assert_eq!(input.len(), 20);
+
+    c.bench_function("sm", |b| {
+        b.iter(|| {
+            let mut count = 0;
+            black_box(sm(input.as_slice(), &mut count))
+        })
+    });
+}
+
+fn bench_30(c: &mut Criterion) {
+    let mut rng = thread_rng();
+
+    let input = {
+        let uniform = Uniform::new(-100.0f32, 100.0f32);
+        uniform.sample_iter(&mut rng).take(30).collect::<Vec<_>>()
+    };
+
+    assert_eq!(input.len(), 30);
+
+    c.bench_function("sm", |b| {
+        b.iter(|| {
+            let mut count = 0;
+            black_box(sm(input.as_slice(), &mut count))
+        })
+    });
+}
+
+fn bench_40(c: &mut Criterion) {
+    let mut rng = thread_rng();
+
+    let input = {
+        let uniform = Uniform::new(-100.0f32, 100.0f32);
+        uniform.sample_iter(&mut rng).take(40).collect::<Vec<_>>()
+    };
+
+    assert_eq!(input.len(), 40);
+
+    c.bench_function("sm", |b| {
+        b.iter(|| {
+            let mut count = 0;
+            black_box(sm(input.as_slice(), &mut count))
+        })
+    });
+}
+
+fn bench_50(c: &mut Criterion) {
+    let mut rng = thread_rng();
+
+    let input = {
+        let uniform = Uniform::new(-100.0f32, 100.0f32);
+        uniform.sample_iter(&mut rng).take(50).collect::<Vec<_>>()
+    };
+
+    assert_eq!(input.len(), 50);
+
+    c.bench_function("sm", |b| {
+        b.iter(|| {
+            let mut count = 0;
+            black_box(sm(input.as_slice(), &mut count))
+        })
+    });
+}
+
+criterion_group!(benches, bench_10, bench_20, bench_30, bench_40, bench_50);
+criterion_main!(benches);
-- 
cgit v1.2.3-18-g5258