[vim/vim] sort() with a numeric option converts each item on every comparison (PR #21003)

## Problem

`sort()` with the `"n"`, `"N"` or `"f"` option converts each item to its
number on *every* comparison.  For `"n"` that is a `tv2string()` followed by
`strtod()` per comparison, so sorting a list of numbers turns each number into
a string and parses it back O(n log n) times, which dwarfs the sort itself.

## Solution

Compute the numeric key of each item once, before the sort, and compare the
stored key.  Only the builtin numeric compare modes are touched; `uniq()`,
which passes a bare list item to the compare function rather than the array
element, and the string and user-function paths are unchanged.

Sorting a list of 100000 numbers (min of 3, macOS arm64):

| sort | before | after |
|------|--------|-------|
| `sort(l, 'n')` | 0.205s | 0.017s |
| `sort(l, 'N')` | 0.017s | 0.010s |
| `sort(l, 'f')` | 0.014s | 0.010s |

The result is identical, including that a string is still treated as `0` in
`"n"` mode and that `"N"` keeps full 64-bit precision (the key is a
`varnumber_T`, not a `double`).

<details>
<summary>Benchmark script</summary>

```vim
vim9script
var shuffled: list<number> = []
var seed = 12345
for x in range(100000)
  seed = (seed * 1103515245 + 12345) % 2147483648
  shuffled->add(seed % 1000000)
endfor
var t0 = reltime()
call copy(shuffled)->sort('n')
echo reltimefloat(reltime(t0))
```
</details>

Adds `Test_sort_numeric_precomputed()`: a large shuffled list sorted with
`"n"`, mixed integers and floats, int64 values beyond the exact range of a
double for `"N"`, and `uniq()` over the non-precomputed path.

AI assistance is acknowledged with Co-Authored-By trailers on the commit,
per AGENTS.md.

You can view, comment on, or merge this pull request online at:

  https://github.com/vim/vim/pull/21003

-- Commit Summary --

  * sort() with a numeric option converts each item on every comparison

-- File Changes --

    M src/list.c (85)
    M src/testdir/test_sort.vim (28)

-- Patch Links --

https://github.com/vim/vim/pull/21003.patch
https://github.com/vim/vim/pull/21003.diff

-- 
Reply to this email directly or view it on GitHub:
https://github.com/vim/vim/pull/21003
You are receiving this because you are subscribed to this thread.

Message ID: <vim/vim/pull/[email protected]>

-- 
-- 
You received this message from the "vim_dev" maillist.
Do not top-post! Type your reply below the text you are replying to.
For more information, visit http://www.vim.org/maillist.php

--- 
You received this message because you are subscribed to the Google Groups "vim_dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
To view this discussion visit https://groups.google.com/d/msgid/vim_dev/vim/vim/pull/21003%40github.com.