Stalin-Sort using Divide&Conquer

package stalin;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * Stalin-Sort is an impractical algorithm for bringing data structures into order.
 *
 * <p>
 * Idea by: <code>@mathew@mastodon.social</code>.
 *
 * <p>
 * <img src="https://i.redd.it/x9triplll1v11.jpg" width=360 height=198 alt="I
 * came up with a single pass O(n) sort algorithm I call Stalin-Sort. U iterate
 * down the list of elements checking if they are in order. Any element which is
 * out of order is eliminated. At the end u have a sorted list"/>
 *
 * <p>
 * However, this does not specify how exactly the elements are chosen. For
 * example for the input <code>[42,1,2,3,4,5,6]</code> you just get
 * <code>[42]</code> instead of <code>[1,2,3,4,5,6]</code>. You can get a better
 * result if you use <i>divide and conquer</i>. And that is something Stalin
 * would do, don't you think? So this is the recursive solution, implemented in
 * Java. It tries all possible results, which is not a single pass and therefore
 * defeats the purpose of having a fast algorithm. And none of these are
 * in-place, so a new data structure has to be created. That's why I added an
 * implementation using a {@link LinkedList}.
 * <p>
 * There are 5 public static methods:
 * <ul>
 * <li>{@link #sort(int[])}: sort integers in <code>O(n)</code>
 * <li>{@link #sortDC(int[])} sort integers using <i>divide and conquer</i>
 * <li>{@link #sort(List)}: sort any List in <code>O(n)</code>
 * <li>{@link #sortDC(List)} sort any List using <i>divide and conquer</i>
 * <li>{@link #inplace(LinkedList)} implementation of the original idea</i>
 * </ul>
 *
 * @author Claude Martin
 *
 */
public class StalinSort {
  /**
   * Naive implementation of Stalin-Sort for integers. It works but it does not
   * return the longest possible array. It's not exactly in <code>O(n)</code>
   * because the resulting array has to be created.
   */
  public static int[] sort(final int[] integers) {
    var previous = Integer.MIN_VALUE;
    final var accepted = new boolean[integers.length];
    var newLen = 0;
    for (var i = 0; i < integers.length; i++) {
      final var value = integers[i];
      if (previous < value) {
        final var next = i + 1 < integers.length ? integers[i + 1] : Integer.MAX_VALUE;
        if (next > previous && next < value) {
          // Eliminate this one and keep the next one instead.
        } else {
          accepted[i] = true;
          newLen++;
          previous = value;
        }
      } // else: Eliminate (not accepted)
    }
    final var result = new int[newLen];
    for (int i = 0, j = 0; i < accepted.length; i++) {
      if (accepted[i])
        result[j++] = integers[i];
    }
    return result;
  }

  /**
   * Improved implementation of Stalin-Sort for integers to find the best
   * solution. Uses <i>divide and conquer</i> to solve this problem. This is not
   * in <code>O(n)</code>. More like <code>O(n log<sub>n</sub>)</code>.
   */
  public static int[] sortDC(final int[] input) {
    final boolean[] accepted = new boolean[input.length];
    final int newLen = _sortDC(input, 0, accepted, 0, Integer.MIN_VALUE);
    final var result = new int[newLen];
    for (int i = 0, j = 0; i < input.length; i++) {
      if (accepted[i])
        result[j++] = input[i];
    }
    return result;
  }

  /**
   * Recursive Stalin-Sort with <i>divide and conquer</i>.
   *
   * @param input
   *          the original input (never changes)
   * @param position
   *          the position of the value to be accepted or eliminated
   * @param accepted
   *          bit set of already accepted values, which will be updated.
   * @return the length of the result. the longer one always wins.
   */
  private static int _sortDC(final int[] input, final int position, final boolean[] accepted, final int count,
      final int lastAccepted) {
    final var len = input.length;
    // System.out.println(String.format("%s = %d", Arrays.toString(accepted),
    // count));
    if (len == position)
      return count;

    if (position > 0 && input[position] < lastAccepted) {
      // input[position] has to be eliminated.
      return _sortDC(input, 1 + position, accepted, count, lastAccepted);
    }
    // First try: eliminate the value
    final var accepted1 = Arrays.copyOf(accepted, len);
    // accepted1[position] = false;
    final int result1 = _sortDC(input, 1 + position, accepted1, count, lastAccepted);
    // Second try: accept the value
    final var accepted2 = Arrays.copyOf(accepted, len);
    accepted2[position] = true;
    final int result2 = _sortDC(input, 1 + position, accepted2, 1 + count, input[position]);

    // Which one is better?
    if (result2 > result1) {
      System.arraycopy(accepted2, 0, accepted, 0, len);
      return result2;
    } else {
      System.arraycopy(accepted1, 0, accepted, 0, len);
      return result1;
    }
  }

  /**
   * Naive implementation of Stalin-Sort. This always creates a new list (not
   * in-place!). It works but it does not return the longest possible list. Works
   * great with linked lists. But no support for <code>null</code>.
   */
  public static <T extends Comparable<? super T>> List<T> sort(final List<T> input) {
    final int size = input.size();
    if (size < 2)
      return new ArrayList<>(input);
    T previous = input.get(0);
    final var result = new ArrayList<T>(size);
    result.add(previous);
    for (var i = 1; i < size; i++) {
      final var value = input.get(i);
      if (previous.compareTo(value) < 0) {
        result.add(previous = value);
      }
    }
    return result;
  }

  /**
   * Improved implementation of Stalin-Sort to find the best solution. Uses
   * <i>divide and conquer</i> to solve this problem. This is not in
   * <code>O(n)</code>. More like <code>O(n log<sub>n</sub>)</code>.
   */
  public static <T extends Comparable<? super T>> List<T> sortDC(final List<T> input) {
    final boolean[] accepted = new boolean[input.size()];
    final int newLen = _sortDC(input, 0, accepted, 0, null);
    final var result = new ArrayList<T>(newLen);
    for (int i = 0; i < input.size(); i++) {
      if (accepted[i])
        result.add(input.get(i));
    }
    return result;
  }

  /**
   * Recursive Stalin-Sort with <i>divide and conquer</i>. Does not support
   * <code>null</code>.
   *
   * @param input
   *          the original input (never changes)
   * @param position
   *          the position of the value to be accepted or eliminated
   * @param accepted
   *          bit set of already accepted values, which will be updated.
   * @return the length of the result. the longer one always wins.
   */
  private static <T extends Comparable<? super T>> int _sortDC(final List<T> input, final int position,
      final boolean[] accepted, final int count, final T lastAccepted) {
    final var len = input.size();
    if (len == position)
      return count;
    if (position > 0 && lastAccepted != null && input.get(position).compareTo(lastAccepted) < 0) {
      // input[position] has to be eliminated.
      return _sortDC(input, 1 + position, accepted, count, lastAccepted);
    }
    // First try: eliminate the value
    final var accepted1 = Arrays.copyOf(accepted, len);
    // accepted1[position] = false;
    final int result1 = _sortDC(input, 1 + position, accepted1, count, lastAccepted);
    // Second try: accept the value
    final var accepted2 = Arrays.copyOf(accepted, len);
    accepted2[position] = true;
    final int result2 = _sortDC(input, 1 + position, accepted2, 1 + count, input.get(position));

    // Which one is better?
    if (result2 > result1) {
      System.arraycopy(accepted2, position, accepted, position, len - position);
      return result2;
    } else {
      System.arraycopy(accepted1, position, accepted, position, len - position);
      return result1;
    }
  }

  /**
   * This is the Stalin-Sort as it should be. Use this for best performance. Does
   * not support <code>null</code>.
   */
  public static <T extends Comparable<? super T>> void inplace(LinkedList<T> input) {
    final var iterator = input.iterator();
    if (!iterator.hasNext())
      return;
    var previous = iterator.next();
    while (iterator.hasNext()) {
      var value = iterator.next();
      if (value.compareTo(previous) < 0)
        iterator.remove();
      else
        previous = value;
    }
  }

  /**
   * Entry point to show that and how it works.
   *
   * @param args
   *          you can give a list of strings to be sorted (optional)
   */
  public static void main(final String[] args) {
    if (args.length > 0) {
      System.out.println("Using your input to demonstrate Stalin-Sort.");
      final var list = new LinkedList<>(List.of(args));
      System.out.println("Input:\t\t" + list);
      System.out.println("Naive:\t\t" + sort(list));
      System.out.println("Div&Conq:\t" + sortDC(list));
      inplace(list);
      System.out.println("in-place:\t" + list);
    } else {
      final int[] array = { 0, 1, 2, -123, 6, 7, 8, 3, 0, 4, 5, 6 };
      System.out.println("Demonstration of Stalin-Sort using integers and Strings.");
      System.out.println("Input:\t\t" + Arrays.toString(array));
      System.out.println("Naive:\t\t" + Arrays.toString(sort(array)));
      System.out.println("Div&Conq:\t" + Arrays.toString(sortDC(array)));
      System.out.println("========================");
      final var list = new LinkedList<>(List.of("A", "B", "x", "Ab", "y", "A", "", "A", "A", "A", "A", "z", "A"));
      System.out.println("Input:\t\t" + list);
      System.out.println("Naive:\t\t" + sort(list));
      System.out.println("Div&Conq:\t" + sortDC(list));
      inplace(list);
      System.out.println("in-place:\t" + list);
    }
  }
}