CachedSort for Java, BSD-0

CachedSort.java

// Copyright (C) 2026 by Qther <qther@tuta.io>
//
// Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted.
//
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.function.*;

public class CachedSort {
    private static final long LONG_LOWER_HALF = 0xFFFF_FFFFL;
    private static final long LONG_UPPER_HALF = ~LONG_LOWER_HALF;
    private static final int INT_LOWER_HALF = 0xFFFF;
    private static final int INT_UPPER_HALF = ~INT_LOWER_HALF;

    /**
     * Sorts {@code list} in-place in ascending order according to the value obtaining by transforming each element into an {@link int} via {@code transform}.
     * <p> 
     * Sort in descending order by using bitwise-not (~) on the result of {@code transform}.
     *
     * @param list      The list to sort
     * @param transform An {@link int} transform function applied to each element in {@code list}
     * @param <T>       The type of the elements in {@code list}
     */
    public static <T> void sortByCachedIntKey(List<T> list, ToIntFunction<T> transform) {
        var size = list.size();
        if (size <= 1) {
            return;
        }

        if (size == 2) {
            if (transform.applyAsInt(list.get(0)) > transform.applyAsInt(list.get(1))) {
                Collections.swap(list, 0, 1);
            }
            return;
        }

        long[] indices = new long[size];
        for (int i = 0; i < size; i++) {
            indices[i] = ((long) transform.applyAsInt(list.get(i)) << 32L) | i;
        }

        Arrays.sort(indices);
        for (int i = 0; i < size; i++) {
            int index = (int) (indices[i] & LONG_LOWER_HALF);
            while (index < i) {
                index = (int) (indices[index] & LONG_LOWER_HALF);
            }
            indices[i] = (indices[i] & LONG_UPPER_HALF) | index;
            Collections.swap(list, i, index);
        }
    }

    @FunctionalInterface
    public interface ToShortFunction<T> {
        /**
         * Applies this function to the given argument.
         *
         * @param value the function argument
         * @return the function result
         */
        short applyAsShort(T value);
    }

    /**
     * Sorts {@code list} in-place in ascending order according to the value obtaining by transforming each element into a {@link short} via {@code transform}.
     * <p>
     *  Sort in descending order by using bitwise-not (~) on the result of {@code transform}.
     *
     * @param list      The list to sort
     * @param transform A {@link short} transform function applied to each element in {@code list}
     * @param <T>       The type of the elements in {@code list}
     */
    public static <T> void sortByCachedShortKey(List<T> list, ToShortFunction<T> transform) {
        var size = list.size();
        if (size <= 1) {
            return;
        }

        if (size == 2) {
            if (transform.applyAsShort(list.get(0)) > transform.applyAsShort(list.get(1))) {
                Collections.swap(list, 0, 1);
            }
            return;
        }

        if (size > 65536) {
            sortByCachedIntKey(list, transform::applyAsShort);
            return;
        }

        int[] indices = new int[size];
        for (int i = 0; i < size; i++) {
            indices[i] = ((int) transform.applyAsShort(list.get(i)) << 16) | i;
        }

        Arrays.sort(indices);
        for (int i = 0; i < size; i++) {
            int index = indices[i] & INT_LOWER_HALF;
            while (index < i) {
                index = indices[index] & INT_LOWER_HALF;
            }
            indices[i] = (indices[i] & INT_UPPER_HALF) | index;
            Collections.swap(list, i, index);
        }
    }

    /**
     * Sorts {@code list} in-place in ascending order according to the value obtaining by transforming each element into a {@link Comparable} via {@code transform}.
     *
     * @param list      The list to sort
     * @param transform A transform function applied to each element in {@code list}
     * @param <T>       The type of the elements in {@code list}
     */
    public static <T, U extends Comparable<U>> void sortByCachedKey(List<T> list, Function<T, U> transform) {
        var size = list.size();
        if (size <= 1) {
            return;
        }

        if (size == 2) {
            if (transform.apply(list.get(0)).compareTo(transform.apply(list.get(1))) > 0) {
                Collections.swap(list, 0, 1);
            }
            return;
        }

        final class Pair implements Comparable<Pair> {
            private final U key;
            private int index;

            Pair(U key, int index) {
                this.key = key;
                this.index = index;
            }

            @Override
            public int compareTo(Pair o) {
                return this.key.compareTo(o.key);
            }
        }

        Pair[] indices = new Pair[size];
        for (int i = 0; i < size; i++) {
            indices[i] = new Pair(transform.apply(list.get(i)), i);
        }

        Arrays.sort(indices);
        for (int i = 0; i < size; i++) {
            int index = indices[i].index;
            while (index < i) {
                index = indices[index].index;
            }
            indices[i].index = index;
            Collections.swap(list, i, index);
        }
    }

    /**
     * Sorts {@code list} in-place in descending order according to the value obtaining by transforming each element into a {@link Comparable} via {@code transform}.
     *
     * @param list      The list to sort
     * @param transform A transform function applied to each element in {@code list}
     * @param <T>       The type of the elements in {@code list}
     */
    public static <T, U extends Comparable<U>> void sortByCachedKeyDescending(List<T> list, Function<T, U> transform) {
        var size = list.size();
        if (size <= 1) {
            return;
        }

        if (size == 2) {
            if (-transform.apply(list.get(0)).compareTo(transform.apply(list.get(1))) > 0) {
                Collections.swap(list, 0, 1);
            }
            return;
        }

        final class Pair implements Comparable<Pair> {
            private final U key;
            private int index;

            Pair(U key, int index) {
                this.key = key;
                this.index = index;
            }

            @Override
            public int compareTo(Pair o) {
                return -this.key.compareTo(o.key);
            }
        }

        Pair[] indices = new Pair[size];
        for (int i = 0; i < size; i++) {
            indices[i] = new Pair(transform.apply(list.get(i)), i);
        }

        Arrays.sort(indices);
        for (int i = 0; i < size; i++) {
            int index = indices[i].index;
            while (index < i) {
                index = indices[index].index;
            }
            indices[i].index = index;
            Collections.swap(list, i, index);
        }
    }

    /**
     * Sorts {@code list} in-place in ascending order according to the value obtaining by transforming each element into a different type via {@code transform}
     * then comparing them using {@code comparator}.
     * <p> 
     * Sort in descending order by reversing the output of {@code comparator}
     *
     * @param list       The list to sort
     * @param transform  A transform function applied to each element in {@code list}
     * @param comparator A function following the contract of {@link Comparable#compareTo(Object)}.
     * @param <T>        The type of the elements in {@code list}
     */
    public static <T, U> void sortByCachedKey(List<T> list, Function<T, U> transform, ToIntBiFunction<U, U> comparator) {
        var size = list.size();
        if (size <= 1) {
            return;
        }

        if (size == 2) {
            if (comparator.applyAsInt(transform.apply(list.get(0)), transform.apply(list.get(1))) > 0) {
                Collections.swap(list, 0, 1);
            }
            return;
        }

        final class Pair implements Comparable<Pair> {
            private final U key;
            private int index;

            Pair(U key, int index) {
                this.key = key;
                this.index = index;
            }

            @Override
            public int compareTo(Pair o) {
                return comparator.applyAsInt(this.key, o.key);
            }
        }

        Pair[] indices = new Pair[size];
        for (int i = 0; i < size; i++) {
            indices[i] = new Pair(transform.apply(list.get(i)), i);
        }

        Arrays.sort(indices);
        for (int i = 0; i < size; i++) {
            int index = indices[i].index;
            while (index < i) {
                index = indices[index].index;
            }
            indices[i].index = index;
            Collections.swap(list, i, index);
        }
    }
}