stable sorting algorithm for 4 elements, with 5 comparisons and 5 swaps

Question

Is there a short, stable sorting algoritm for 4 elements with 5 comparisons and 5 swaps?

I'm looking for an algorithm like https://stackoverflow.com/a/50303723/97248 in terms of length and complexity, but which is stable. This one is not stable: for example, for input [60, 61, 52, 73], with comparison function which ignores the last digit, the result is [52, 61, 60, 73], and the correct stable result would be [52, 60, 61, 73].

Answer 1

It seems to be possible if we track swaps that could (potentially) introduce an inversion of two equal values. This can happen when a swap concerns non-adjacent values, which will be needed at least once if we want to keep the number of comparisons/swaps at five. Such potential inversion will then determine whether a next comparison should be done with > or >=.

To test "stableness", I tested with (key, index) pairs where only the keys influence the comparison, while the index can be used to verify that the original relative order was not altered when keys are the same.

Here is an implementation in JavaScript:

function sort(arr)  {
    function swapIfGreater(arr, i, j, orEqual) {
        const isGreater = orEqual ? arr[i][0] >= arr[j][0] : arr[i][0] > arr[j][0];
        if (isGreater) [arr[i], arr[j]] = [arr[j], arr[i]]; // swap
        return isGreater;
    }
    // 5 calls to swapIfGreater:
    swapIfGreater(arr, 1, 2, false);
    const outerInversion = swapIfGreater(arr, 0, 3, false);
    const innerInversion1 = swapIfGreater(arr, 0, 1, outerInversion);
    const innerInversion2 = swapIfGreater(arr, 2, 3, outerInversion);
    swapIfGreater(arr, 1, 2, (innerInversion1 || innerInversion2) && outerInversion);
}

function verify(arr) {
    for (let i = 1; i < arr.length; i++) {
        const diff = arr[i][0] - arr[i-1][0] || arr[i][1] - arr[i-1][1];
        if (diff < 0) throw "Not sorted correctly!";
    }
}

function tagWithIndex(arr) { // To detect inversions of equal values
    for (let i = 0; i < arr.length; i++) {
        arr[i] = [arr[i], i]; // Entry becomes a pair: the value, and the index
    }
}

// Test all possibilities of unordered inputs:
for (let a = 0; a < 4; a++) {
    for (let b = 0; b < 4; b++) {
        for (let c = 0; c < 4; c++) {
            for (let d = 0; d < 4; d++) {
                const arr = [a, b, c, d];
                tagWithIndex(arr);
                sort(arr);
                verify(arr);
            }
        }
    }
}

console.log("all tests passed");

Note that the inversion variables are only there to avoid a nested tree of if ... else blocks to mimic the same states.

Answer 2

This answer is inspired by the comment of @JimMischel. It implements stable sorting of 4 elements with at most 5 comparisons and 6 swaps. It's a Python implementation of the variant of insertion sort which uses binary search to find the insertion location.

def stable_sort4(a):
  if len(a) != 4:
    raise ValueError
  if a[1] // 10 < a[0] // 10:
    a[1], a[0] = a[0], a[1]
  if a[2] // 10 < a[1] // 10:
    a[2], a[1] = a[1], a[2]
    if a[1] // 10 < a[0] // 10:
      a[1], a[0] = a[0], a[1]
  if a[3] // 10 < a[1] // 10:
    if a[3] // 10 < a[0] // 10:
      a[3], a[2] = a[2], a[3]  # Swap #4.
      a[2], a[1] = a[1], a[2]  # Swap #5.
      a[1], a[0] = a[0], a[1]  # Swap #6.
    else:
      a[3], a[2] = a[2], a[3]
      a[2], a[1] = a[1], a[2]
  elif a[3] // 10 < a[2] // 10:
    a[3], a[2] = a[2], a[3]


def test():
  for i0 in range(4):
    for i1 in range(4):
      for i2 in range(4):
        for i3 in range(4):
          a = [i0 * 10, i1 * 10 + 1, i2 * 10 + 2, i3 * 10 + 3]
          stable_sort4(a)
          if a != sorted(a):
            raise AssertionError(a)


if __name__ == '__main__':
  test()

This algorithm always swaps adjacent elements, each swap decreasing the total inversion count by 1. If the input is reversed, then initially there are 3 + 2 + 1 == 6 inversions, thus any algorithm which swaps adjacent elements only must do at least 6 swaps. Equivalently, to solve it with 5 swaps, we need an algorithm (such as the one in @trincot's answer) which sometimes swaps non-adjacent elements.