Improve the performance of `Data.List.sort` further

I believe that I slightly improved the performance of `Data.List.sort` by changing its internal `sequences` function. My version takes a look at the first three elements of the input (instead of two), locally sorts them, and invokes `ascending` or `descending` only when these elements are weakly increasing or strictly decreasing, respectively.

I [forked](https://github.com/pi8027/ghc-sort-perf) @cbrt-x's [sort-perf](https://github.com/cbrt-x/sort-perf) repo (cf. #236) and added a mergesort function implementing my proposal (`app/Sorts/New3N.hs` in the repo, and `New3N` below). I obtained the following benchmark result. It corresponds to the commit `743944a` in my fork.
```
All
List tests
correctness
Old (GHC < 9.12.1, 2-way merge): OK
+++ OK, passed 100 tests.
New (GHC >= 9.12.1, 4-way merge): OK
+++ OK, passed 100 tests.
New3N: OK
+++ OK, passed 100 tests.
New4N: OK
+++ OK, passed 100 tests.
stability
Old (GHC < 9.12.1, 2-way merge): OK
+++ OK, passed 100 tests.
New (GHC >= 9.12.1, 4-way merge): OK
+++ OK, passed 100 tests.
New3N: OK
+++ OK, passed 100 tests.
New4N: OK
+++ OK, passed 100 tests.
1 Elements
sort
Old (GHC < 9.12.1, 2-way merge): OK
85.0 ns ± 5.7 ns, 0.98x
New (GHC >= 9.12.1, 4-way merge): OK
87.1 ns ± 5.3 ns
New3N: OK
86.4 ns ± 5.9 ns, 0.99x
New4N: OK
85.9 ns ± 6.6 ns, 0.99x
comparisons
Old (GHC < 9.12.1, 2-way merge): OK
0 comparisons
New (GHC >= 9.12.1, 4-way merge): OK
0 comparisons
New3N: OK
0 comparisons
New4N: OK
0 comparisons
min by sort
Old (GHC < 9.12.1, 2-way merge): OK
90.9 ns ± 5.7 ns, 0.97x
New (GHC >= 9.12.1, 4-way merge): OK
93.4 ns ± 6.0 ns
New3N: OK
98.7 ns ± 6.2 ns, 1.06x
New4N: OK
93.8 ns ± 6.0 ns, 1.00x
5 Elements
sort
Old (GHC < 9.12.1, 2-way merge): OK
428 ns ± 14 ns, 1.11x
New (GHC >= 9.12.1, 4-way merge): OK
384 ns ± 21 ns
New3N: OK
342 ns ± 26 ns, 0.89x
New4N: OK
282 ns ± 22 ns, 0.73x
comparisons
Old (GHC < 9.12.1, 2-way merge): OK
7 comparisons
New (GHC >= 9.12.1, 4-way merge): OK
7 comparisons
New3N: OK
7 comparisons
New4N: OK
6 comparisons
min by sort
Old (GHC < 9.12.1, 2-way merge): OK
328 ns ± 22 ns, 1.08x
New (GHC >= 9.12.1, 4-way merge): OK
305 ns ± 23 ns
New3N: OK
265 ns ± 22 ns, 0.87x
New4N: OK
249 ns ± 22 ns, 0.82x
25 Elements
sort
Old (GHC < 9.12.1, 2-way merge): OK
4.59 μs ± 364 ns, 1.56x
New (GHC >= 9.12.1, 4-way merge): OK
2.95 μs ± 173 ns
New3N: OK
2.67 μs ± 179 ns, 0.91x
New4N: OK
2.32 μs ± 183 ns, 0.79x
comparisons
Old (GHC < 9.12.1, 2-way merge): OK
99 comparisons
New (GHC >= 9.12.1, 4-way merge): OK
99 comparisons
New3N: OK
97 comparisons
New4N: OK
88 comparisons
min by sort
Old (GHC < 9.12.1, 2-way merge): OK
1.53 μs ± 99 ns, 1.40x
New (GHC >= 9.12.1, 4-way merge): OK
1.09 μs ± 94 ns
New3N: OK
926 ns ± 92 ns, 0.85x
New4N: OK
783 ns ± 43 ns, 0.72x
100 Elements
sort
Old (GHC < 9.12.1, 2-way merge): OK
29.4 μs ± 2.8 μs, 1.61x
New (GHC >= 9.12.1, 4-way merge): OK
18.2 μs ± 1.5 μs
New3N: OK
16.4 μs ± 806 ns, 0.90x
New4N: OK
16.1 μs ± 1.6 μs, 0.88x
comparisons
Old (GHC < 9.12.1, 2-way merge): OK
605 comparisons
New (GHC >= 9.12.1, 4-way merge): OK
602 comparisons
New3N: OK
578 comparisons
New4N: OK
562 comparisons
min by sort
Old (GHC < 9.12.1, 2-way merge): OK
6.13 μs ± 370 ns, 1.40x
New (GHC >= 9.12.1, 4-way merge): OK
4.39 μs ± 424 ns
New3N: OK
3.36 μs ± 173 ns, 0.77x
New4N: OK
3.05 μs ± 169 ns, 0.69x
1000 Elements
sort
Old (GHC < 9.12.1, 2-way merge): OK
513 μs ± 44 μs, 1.41x
New (GHC >= 9.12.1, 4-way merge): OK
364 μs ± 22 μs
New3N: OK
347 μs ± 23 μs, 0.95x
New4N: OK
332 μs ± 27 μs, 0.91x
comparisons
Old (GHC < 9.12.1, 2-way merge): OK
9199 comparisons
New (GHC >= 9.12.1, 4-way merge): OK
9163 comparisons
New3N: OK
8984 comparisons
New4N: OK
8723 comparisons
min by sort
Old (GHC < 9.12.1, 2-way merge): OK
63.2 μs ± 5.8 μs, 1.31x
New (GHC >= 9.12.1, 4-way merge): OK
48.1 μs ± 2.7 μs
New3N: OK
37.1 μs ± 3.1 μs, 0.77x
New4N: OK
36.0 μs ± 1.6 μs, 0.75x
10000 Elements
sort
Old (GHC < 9.12.1, 2-way merge): OK
9.58 ms ± 699 μs, 1.63x
New (GHC >= 9.12.1, 4-way merge): OK
5.87 ms ± 337 μs
New3N: OK
5.32 ms ± 414 μs, 0.91x
New4N: OK
5.44 ms ± 450 μs, 0.93x
comparisons
Old (GHC < 9.12.1, 2-way merge): OK
132731 comparisons
New (GHC >= 9.12.1, 4-way merge): OK
125105 comparisons
New3N: OK
122380 comparisons
New4N: OK
122679 comparisons
min by sort
Old (GHC < 9.12.1, 2-way merge): OK
734 μs ± 45 μs, 1.39x
New (GHC >= 9.12.1, 4-way merge): OK
530 μs ± 21 μs
New3N: OK
438 μs ± 42 μs, 0.83x
New4N: OK
445 μs ± 23 μs, 0.84x
100000 Elements
sort
Old (GHC < 9.12.1, 2-way merge): OK
279 ms ± 4.1 ms, 1.84x
New (GHC >= 9.12.1, 4-way merge): OK
151 ms ± 15 ms
New3N: OK
120 ms ± 12 ms, 0.79x
New4N: OK
114 ms ± 5.4 ms, 0.75x
comparisons
Old (GHC < 9.12.1, 2-way merge): OK
1609697 comparisons
New (GHC >= 9.12.1, 4-way merge): OK
1600246 comparisons
New3N: OK
1544779 comparisons
New4N: OK
1553192 comparisons
min by sort
Old (GHC < 9.12.1, 2-way merge): OK
16.5 ms ± 1.1 ms, 1.43x
New (GHC >= 9.12.1, 4-way merge): OK
11.5 ms ± 707 μs
New3N: OK
7.91 ms ± 427 μs, 0.69x
New4N: OK
6.06 ms ± 496 μs, 0.53x
1000000 Elements
sort
Old (GHC < 9.12.1, 2-way merge): OK
4.370 s ± 6.4 ms, 1.64x
New (GHC >= 9.12.1, 4-way merge): OK
2.662 s ± 85 ms
New3N: OK
2.541 s ± 77 ms, 0.95x
New4N: OK
2.360 s ± 29 ms, 0.89x
comparisons
Old (GHC < 9.12.1, 2-way merge): OK
19237495 comparisons
New (GHC >= 9.12.1, 4-way merge): OK
19166437 comparisons
New3N: OK
18860801 comparisons
New4N: OK
18709759 comparisons
min by sort
Old (GHC < 9.12.1, 2-way merge): OK
209 ms ± 19 ms, 1.46x
New (GHC >= 9.12.1, 4-way merge): OK
143 ms ± 9.7 ms
New3N: OK
125 ms ± 3.8 ms, 0.87x
New4N: OK
109 ms ± 9.6 ms, 0.76x

All 104 tests passed (121.61s)
```

- `New3N` is almost always (except `1 Elements` -> `min by sort`) faster and performs fewer comparisons than the current `Data.List.sort` (`New` above).
- `New4N` locally sorts four elements instead of three, but it's not always better than `New3N`.

To give some context, I drew inspiration from OCaml's `List.sort` function, which is a non-smooth top-down tail-recursive mergesort function. When the list to be sorted has fewer than four elements, it stops the recursion and sorts the elements locally. I discovered this improvement while writing [our ICFP'25 paper](https://arxiv.org/abs/2403.08173) on formally and modularly proving the functional correctness of several variants of mergesort.

Another thing I know is that tail-recursive mergesorts are a lot faster than non-tail-recursive ones (like `Data.List.sort`) when we don't need laziness (*i.e.*, when we need the entire sorted list immediately). I guess it's a nice addition to a standard-ish Haskell library supporting strict computation, but I'm unsure to which library I should contribute it.

Start by reviewing Data.List.sort and the proposed implementation in app/Sorts/New3N.hs from the linked sort-perf fork. Compare the New3N and New4N correctness, stability, benchmark, and comparison results, then determine which library should own a strict tail-recursive variant. Done requires an agreed design and validated performance and correctness evidence.

Written by the indexing model from the issue text.