de.caff.generics.algorithm

Class FastSortByte

java.lang.Object

de.caff.generics.algorithm.FastSortByte

class FastSortByte
extends java.lang.Object

A non-stable sort algorithm for byte arrays which is much faster compared to TimSort. This algorithm is making advantage that there are just 256 distinct byte values, so for larger arrays it is simpler to count the bytes.

It also uses a best-of-3 pivot selection for partitioning during quicksort, which is slower than DualPivotQuicksort but much simpler.

Since:

January 25, 2023

Author:

Rammi

Constructor Summary

Constructors

Constructor and Description
FastSortByte()

Method Summary

Modifier and Type	Method and Description
(package private) static void	quickSort(MutableByteIndexable elements, ByteOrdering order)
static void	sort(byte[] bytes) Sort the given byte array in natural order.
static void	sort(byte[] bytes, ByteOrdering order) Sort the given byte array in user-defined order.
static void	sort(byte[] bytes, int startIndex, int length) Sort a part of the given byte array in natural order.
static void	sort(byte[] bytes, int startIndex, int length, ByteOrdering order) Sort a part of the given byte array in user-defined order.
static void	sort(MutableByteIndexable bytes) Sort the given mutable byte indexable in natural order.
static void	sort(MutableByteIndexable bytes, ByteOrdering order) Sort the given mutable byte indexable using the given ordering.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

FastSortByte

FastSortByte()

Method Detail

sort

public static void sort(@NotNull
                        byte[] bytes)

Sort the given byte array in natural order. This will forward to Arrays.sort(byte[]).

Parameters:

bytes - byte array

sort

public static void sort(@NotNull
                        byte[] bytes,
                        @NotNull
                        ByteOrdering order)

Sort the given byte array in user-defined order. This will forward to Arrays.sort(byte[]).

Parameters:

bytes - byte array

order - sort order

sort

public static void sort(@NotNull
                        byte[] bytes,
                        int startIndex,
                        int length)

Sort a part of the given byte array in natural order. This will forward to Arrays.sort(byte[],int,int).

Parameters:

bytes - byte array

startIndex - start index into the byte array where the part to be sorted begins

length - length of the part to be sorted

sort

public static void sort(@NotNull
                        byte[] bytes,
                        int startIndex,
                        int length,
                        @NotNull
                        ByteOrdering order)

Sort a part of the given byte array in user-defined order. This will forward to Arrays.sort(byte[],int,int).

Parameters:

bytes - byte array

startIndex - start index into the byte array where the part to be sorted begins

length - length of the part to be sorted

order - sort order

sort

public static void sort(@NotNull
                        MutableByteIndexable bytes)

Sort the given mutable byte indexable in natural order.

Parameters:

bytes - byte indexable

sort

public static void sort(@NotNull
                        MutableByteIndexable bytes,
                        @NotNull
                        ByteOrdering order)

Sort the given mutable byte indexable using the given ordering.

Parameters:

bytes - byte indexable

order - sort order

quickSort

static void quickSort(@NotNull
                      MutableByteIndexable elements,
                      @NotNull
                      ByteOrdering order)