Here's an idea: if you're on Linux, use this to sort the list of all paths on your file system (find / -xdev). It's a nice dataset since it's (a) a large list, (b) comparisons are nontrivial, and (c) it's a realistic mix of somewhat-sorted-but-not-completely. (Note: If the file system already sorts everything this won't do the job, so it won't work on e.g. WSL.)
Sorting strings by generic comparison is very inefficient regardless of the algorithm you choose, especially if the long prefixes repeat, which is the case for FS paths.
