An successful attempt to create a stable, in-place algorithm to partition an array

PartitionTest.java

import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.Matchers.empty;
import static org.hamcrest.Matchers.hasToString;

import java.util.Arrays;
import java.util.Collection;
import java.util.List;
import java.util.Random;
import java.util.function.IntPredicate;
import java.util.stream.Collectors;
import org.hamcrest.Matcher;
import org.junit.jupiter.api.Test;

/** An algorithm to partition an array into regions where a predicate evaluates
 * to true and false.
 *
 * <p>The goal is to work in place (i.e. not requiring a copy of the array
 * or temporary storage) and to be stable (i.e. to preserve the relative
 * order of elements) but the algorithm fails to be stable. I'm not sure
 * that it is possible to meet the goal. */
public class PartitionTest {
  @Test
  void testPartitionArray() {
    IntPredicate even = j -> j % 2 == 0;
    IntPredicate odd = j -> j % 2 == 1;
    IntPredicate never = j -> false;
    IntPredicate always = j -> true;
    String all15 = "[11, 8, 3, 13, 4, 1, 9, 14, 10, 7, 0, 5, 12, 6, 2]";
    String odd15 = "[11, 3, 13, 1, 5, 9, 7]";
    String even15 = "[2, 8, 6, 12, 4, 0, 10, 14]";
    checkPartition(
        15, even, hasToString(all15), hasToString(odd15), hasToString(even15));
    checkPartition(
        15, odd, hasToString(all15), hasToString(even15), hasToString(odd15));
    checkPartition(
        1, even, hasToString("[0]"), hasToString("[]"), hasToString("[0]"));
    checkPartition(0, even, empty(), empty(), empty());
  }

  private static void checkPartition(
      int size,
      IntPredicate intPredicate,
      Matcher<Collection<?>> initialMatcher,
      Matcher<Collection<?>> trueMatcher,
      Matcher<Collection<?>> falseMatcher) {
    long seed = 123L;
    final Random r = new Random(seed);
    final int[] ints = new int[size];
    for (int i = 0; i < ints.length; i++) {
      ints[i] = i;
    }
    // Shuffle the array.
    for (int i = ints.length - 1; i > 0; i--) {
      int j = r.nextInt(i + 1);
      // Simple swap
      int tmp = ints[i];
      ints[i] = ints[j];
      ints[j] = tmp;
    }
    final List<Integer> initialList =
        Arrays.stream(ints).boxed().collect(Collectors.toList());
    assertThat(initialList, initialMatcher);
    final int i = partition(ints, intPredicate);
    final List<Integer> finalList =
        Arrays.stream(ints).boxed().collect(Collectors.toList());
    assertThat(finalList.subList(i, finalList.size()), trueMatcher);
    assertThat(finalList.subList(0, i), falseMatcher);
  }

  static int partition(int[] ints, IntPredicate predicate) {
    if (ints.length == 0) {
      return 0; // Nothing to partition
    }
    int i = 0;
    for (int k = ints.length, c = ints[i]; ; ) {
      if (predicate.test(c)) {
        ints[i] = c;
        ++i;
        if (i == k) {
          break;
        }
        c = ints[i];
      } else {
        --k;
        int nextC = ints[k];
        ints[k] = c;
        if (i == k) {
          break;
        }
        c = nextC;
      }
    }
    // Reverse the order of the upper part (which contains
    // the elements that do not match the predicate).
    for (int j = i, k = ints.length - 1; j < k; j++, k--) {
      int tmp = ints[j];
      ints[j] = ints[k];
      ints[k] = tmp;
    }
    // Return the size of the lower part.
    return i;
  }
}