Queue-mergesort: a mergesort that does optimal number of comparisons in the worst case in Java

Question

Here is the code for queue-mergesort by Mordecai J. Golin and Robert Sedgewick:

com.github.coderodde.util.QueueMergesort.java:

package com.github.coderodde.util;

import java.util.Arrays;
import java.util.Comparator;

/**
 *
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Apr 1, 2023)
 * @since 1.6 (Apr 1, 2023)
 */
public class QueueMergesort {

    private static final class ListItem<E> {
        E datum;
        ListItem<E> next;
        
        ListItem(E datum) {
            this.datum = datum;
        }
    }
    
    private static final class Queue<E> {
        
        private final ListItem<E>[] buffer;
        private int headIndex = 0;
        private int tailIndex = 0;
        private int size = 0;
        
        Queue(int bufferCapacity) {
            this.buffer = new ListItem[bufferCapacity];
        }
        
        int size() {
            return size;
        }
        
        ListItem<E> get() {
            ListItem<E> listHead = buffer[headIndex];
            headIndex = (headIndex + 1) % buffer.length;
            size--;
            return listHead;
        }
        
        void put(ListItem<E> tail) {
            buffer[tailIndex] = tail;
            tailIndex = (tailIndex + 1) % buffer.length;
            size++;
        }
    }
    
    public static <E> void sort(E[] array, Comparator<? super E> comparator) {
        if (array.length < 2) {
            return;
        }
   
        Queue<E> queue = new Queue(array.length);
        
        for (E element : array) {
            queue.put(new ListItem<>(element));
        }
        
        while (queue.size() > 1) {
            ListItem<E> lst1 = queue.get();
            ListItem<E> lst2 = queue.get();
            queue.put(merge(lst1, lst2, comparator));
        }
        
        int index = 0;
        
        for (ListItem<E> list = queue.get(); list != null; list = list.next) {
            array[index++] = list.datum;
        }
    }
    
    private static <E> ListItem<E> merge(ListItem<E> lst1, 
                                         ListItem<E> lst2,
                                         Comparator<? super E> comparator) {
        ListItem<E> mergedList;
        ListItem<E> mergedListTail;
        
        if (comparator.compare(lst1.datum, lst2.datum) <= 0) {
            mergedList = lst1;
            lst1 = lst1.next;
        } else {
            mergedList = lst2;
            lst2 = lst2.next;
        }
        
        mergedListTail = mergedList;
        
        while (lst1 != null && lst2 != null) {
            if (comparator.compare(lst1.datum, lst2.datum) <= 0) {
                mergedListTail.next = lst1;
                mergedListTail = lst1;
                lst1 = lst1.next;
            } else {
                mergedListTail.next = lst2;
                mergedListTail = lst2;
                lst2 = lst2.next;
            }
        }
        
        if (lst1 != null) {
            mergedListTail.next = lst1;
        } else {
            mergedListTail.next = lst2;
        }
        
        return mergedList;
    }
    
    public static void main(String[] args) {
        Integer[] array = { 5, 2, 1, 4, 3 };
        QueueMergesort.sort(array, Integer::compareTo);
        System.out.println(Arrays.toString(array));
    }
}

com.github.coderodde.util.QueueMergesortTest.java:

package com.github.coderodde.util;

import java.util.Arrays;
import java.util.Random;
import static junit.framework.Assert.assertTrue;
import org.junit.Test;

public class QueueMergesortTest {
    
    private static final int TEST_RUNS = 100;
    private static final int MAX_ARRAY_LENGTH = 1_000;
    private static final int UPPER_ELEMENT_BOUND = 600;
    
    @Test
    public void bruteForceTest() {
        Random random = new Random(100L);
        
        for (int i = 0; i < TEST_RUNS; i++) {
            int arrayLength = random.nextInt(MAX_ARRAY_LENGTH) + 1;
            Integer[] array = getRandomArray(arrayLength, random);
            Integer[] referenceArray = array.clone();
            
            com.github.coderodde.util.QueueMergesort.sort(
                    array, 
                    Integer::compareTo);
            
            java.util.Arrays.sort(referenceArray, Integer::compareTo);
            
            assertTrue(Arrays.equals(referenceArray, array));
        }
    }
    
    private static Integer[] getRandomArray(int size, Random random) {
        Integer[] array = new Integer[size];
        
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(UPPER_ELEMENT_BOUND);
        }
        
        return array;
    }
}

Critique request

As always, please tell me anything what comes to mind.

Answer 1

The instantiation of Queue should probably read new Queue<>(array.length) - but why roll your own Queue when the point of the exercise is something else?
If you don't like java.util.Queue<ListItem<E>> for offer() and poll(), create a wrapper.

In merge(), don't repeat yourself.
Bored of introducing a dummy ListItem and setting tail to it:

    /** Merges linked lists of <code>ListItem</code>s according to <code>order</code>.
     * Both <code>list1</code> and <code>list2</code> need to be cycle-free lists.
     * At least one instance member <code>next</code> will be mutated.
     * @returns the merged list */
    private static <E> ListItem<E> 
    merge(ListItem<E> list1, ListItem<E> list2, Comparator<? super E> order) {
        ListItem<E> preferred, deferred, merged, next;
        if (order.compare(list1.datum, list2.datum) <= 0) {
            preferred = list1;
            deferred = list2;
        } else {
            preferred = list2;
            deferred = list1;
        }
        merged = preferred;
        while (true) {
            E challenger = deferred.datum;
            while (true) {
                next = preferred.next;
                if (null == next) {
                    preferred.next = deferred;
                    return merged;
                }
                if (0 < order.compare(next.datum, challenger)) {
                    break;
                }
                preferred = next;
            }
            preferred.next = deferred;
            preferred = deferred; // won compared to next
            deferred = next;
        }
    }

(While preferred.next = deferred; looks common to "both ifs", it would be harmful if the inner loop continues, thus should not be done unconditionally before the first if.
I think it apparent that challenger is dispensable -
there is readability, Occam, and coding the way one thinks about solution.
(I'd expect the average number of trips through the inner loop to be 2.
And execution time to be dominated entirely by pointer chasing once data exceeds cache capacity significantly.))