--- a/share/local-bsdtools/farray.sh	Wed Oct 23 18:33:38 2024 +0200
+++ b/share/local-bsdtools/farray.sh	Wed Oct 23 22:52:14 2024 +0200
@@ -1627,6 +1627,7 @@
 
     _farr_array_get_meta "$@"
 
+    # XXX TBD: Select a method depenting on `__farr_len`.
     _farr_array_gnomesort
 }
 
@@ -1655,6 +1656,8 @@
 #:
 #: Internal sort implementation using Gnome Sort.
 #:
+#: Stable: yes
+#:
 #: This is a very simple stable sort (a variant of insertion sort).
 #:
 #: See: https://en.wikipedia.org/wiki/Gnome_sort
@@ -1692,6 +1695,96 @@
 
 
 #:
+#: Sort an array using Shell Sort.
+#:
+#: Args:
+#:   $1: The array to sort to
+#:
+#: See Also:
+#:   `_farr_array_shellsort`
+#:
+farray_shellsort() {
+    local __farr_name
+
+    local __farr_token __farr_gvrname __farr_len \
+          __farr_pos __farr_val __farr_val_1
+
+    _farr_array_get_meta "$@"
+
+    _farr_array_shellsort
+}
+
+
+#:
+#: Internal sort implementation using Shell Sort.
+#:
+#: Used gap sequence: A102549 (Optimal (best known) sequence of increments
+#:                    for shell sort algorithm.) (aka Ciura gap sequence)
+#:
+#: Stable: no
+#:
+#: See: - https://en.wikipedia.org/wiki/Shellsort
+#:      - https://oeis.org/A102549
+#:
+#: Input (Globals):
+#:   All the "Output (Globals)" from `farr_array_get_meta`:
+#:   __farr_name, __farr_token, __farr_gvrname and __farr_len.
+#:   These variables are declared local in this function but the shell
+#:   initializes them from the same variables in the nearest dynamic scope.
+#:   So they are really input variables and not also output variables.
+#:
+_farr_array_shellsort() {
+
+    local __farr_name __farr_token __farr_gvrname __farr_len \
+          gaps_ciura \
+          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.)
+    #
+    gaps_ciura="1750 701 301 132 57 23 10 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
+        #
+        # Do a gapped insertion sort for every elements in gaps;
+        # each loop leaves a[1..gap] in gapped order
+        #
+        i=$((gap + 1))
+        while [ "${i}" -le "${__farr_len}" ]; do
+            # Save a[i] in temp and make a hole at position i
+            eval tmpitem=\"\$\{"${__farr_gvrname}"_"${i}"\}\"
+            #
+            # Shift earlier gap-sorted elements up until the correct
+            # location for a[i] is found
+            #
+            j="${i}"
+            while true; do
+                [ "${j}" -le "${gap}" ] && break
+                eval tmpgapitem=\"\$\{"${__farr_gvrname}"_$((j - gap))\}\"
+                [ "${tmpgapitem}" = "${tmpitem}" ] || [ "${tmpgapitem}" '<' "${tmpitem}" ] && break
+#                if [ "${tmpgapitem}" = "${tmpitem}" ] || [ "${tmpgapitem}" '<' "${tmpitem}" ] ; then
+#                    break
+                #                fi
+                
+                setvar "${__farr_gvrname}"_"${j}" "${tmpgapitem}"
+                j=$((j - gap))
+            done
+            # Put temp (the original a[i]) in its correct location
+            setvar "${__farr_gvrname}"_"${j}" "${tmpitem}"
+            i=$((i + 1))
+        done
+    done
+}
+
+
+#:
 #: Try to find the index of a given value in an existing array.
 #:
 #: It assumes that the array is sorted and uses a binary search algorithm

--- a/tests/farray-array.t	Wed Oct 23 18:33:38 2024 +0200
+++ b/tests/farray-array.t	Wed Oct 23 22:52:14 2024 +0200
@@ -1402,10 +1402,20 @@
 
   $ farray_create TEST
   $ farray_splice "" TEST 1 "" UNSORTED
+  $ check_array_is_sorted "$TEST"
+  [1]
   $ farray_gnomesort TEST
   $ check_array_is_sorted "$TEST"
   $ farray_release TEST
 
+  $ farray_create TEST
+  $ farray_splice "" TEST 1 "" UNSORTED
+  $ check_array_is_sorted "$TEST"
+  [1]
+  $ farray_shellsort TEST
+  $ check_array_is_sorted "$TEST"
+  $ farray_release TEST
+
   $ farray_release UNSORTED
   $ check_no_array_artifacts