# HG changeset patch
# User Franz Glasner <fzglas.hg@dom66.de>
# Date 1729762531 -7200
# Node ID ff36742b99550f7872968a0d751db6fdd66067a6
# Parent  75a8b69c04f0660540d8284f5bfea47ceadba1dd
farray.sh: For larger arrays use A366726 Shellsort gaps

diff -r 75a8b69c04f0 -r ff36742b9955 share/local-bsdtools/farray.sh
--- a/share/local-bsdtools/farray.sh	Wed Oct 23 22:52:14 2024 +0200
+++ b/share/local-bsdtools/farray.sh	Thu Oct 24 11:35:31 2024 +0200
@@ -1736,22 +1736,34 @@
 _farr_array_shellsort() {
 
     local __farr_name __farr_token __farr_gvrname __farr_len \
-          gaps_ciura \
-          gap i j tmpitem tmpgapitem
+          gaps_ciura gaps_ying_wai_lee \
+          gaps gap i j tmpitem tmpgapitem
 
     #
-    # XXX TBD: For larger length extend with A366726 (which are further
-    #          optimized Tokuda good gaps.
-    #          Or use a completely other sort (heap sort, et al.)
+    # A102549
+    # Optimal (best known) sequence of increments for shell sort algorithm.
     #
     gaps_ciura="1750 701 301 132 57 23 10 4 1"
+    #
+    # A366726
+    # The gaps were found empirically using a generalization of the
+    # formula which generates Tokuda's good gaps (A108870).  These are
+    # a noticeable improvement over Tokuda's sequence when sorting
+    # random data, especially where N is in the millions.
+    #
+    gaps_ying_wai_lee="136655165852 60908635199 27147615084 12099975682 5393085583 2403754591 1071378536 477524607 212837706 94863989 42281871 18845471 8399623 3743800 1668650 743735 331490 147748 65853 29351 13082 5831 2599 1158 516 230 102 45 20 9 4 1"
 
     #
     # Start with the largest gap and work down to a gap of 1 similar
     # to insertion sort but instead of 1, gap is being used in each
     # step
     #
-    for gap in ${gaps_ciura}; do
+    if [ "${__farr_len}" -lt 2599 ]; then
+        gaps="${gaps_ciura}"
+    else
+        gaps="${gaps_ying_wai_lee}"
+    fi
+    for gap in ${gaps}; do
         #
         # Do a gapped insertion sort for every elements in gaps;
         # each loop leaves a[1..gap] in gapped order