Doubly Linked List QuickSort Implementation Problem

Question

I've implemented a classic Doubly Linked List:

class Node<T> {
    protected T data;

    protected Node<T> next, prev;
}

class DoublyLinkedList<T extends Comparable<T>> {
    protected Node<T> front;
    protected Node<T> back;
    protected int size;

    // methods
}

Now in order to be able to sort it I then added the following methods implementing a classic QuickSort algorithm:

public void sort(Comparator<T> comparator) {
    quickSort(front, back, comparator);
}

private void quickSort(Node<T> begin, Node<T> end, Comparator<T> comparator) {
    if (end != null && begin != end && begin != end.next) {
        var temp = partition(begin, end, comparator);
        quickSort(begin, temp.prev, comparator);
        quickSort(temp.next, end, comparator);
    }
}

private Node<T> partition(Node<T> begin, Node<T> end, Comparator<T> comparator) {
    var pivot = end.data;

    var i = begin.prev;
    Node<T> next;

    for (var j = begin; j != end; j = next) {
        next = j.next;
        if (comparator.compare(j.data, pivot) < 0) {
            i = (i == null) ? begin : i.next;

            swapData(i, j);
        }
    }

    i = (i == null) ? begin : i.next;
    swapData(i, end);

    return i;
}

private void swapData(Node<T> a, Node<T> b) {
    var temp = a.data;
    a.data = b.data;
    b.data = temp;
}

The code above produces correct results, however, I decided to swap the nodes instead of data, so I introduced these methods:

private void swapNodes(Node<T> a, Node<T> b) {
    if (a == b) return;

    if (a == null || b == null) {
        throw new NullPointerException();
    }

    if (a.next == b) {
        var before = a.prev;
        var after = b.next;

        link(before, b);
        link(b, a);
        link(a, after);
    } else if (b.next == a) {
        var before = b.prev;
        var after = a.next;

        link(before, a);
        link(a, b);
        link(b, after);
    } else {
        var aPrev = a.prev;
        var aNext = a.next;
        var bPrev = b.prev;
        var bNext = b.next;

        link(aPrev, b);
        link(b, aNext);
        link(bPrev, a);
        link(a, bNext);
    }
}

private void link(Node<T> a, Node<T> b) {
    if (a != null)
        a.next = b;
    else
        front = b;
    if (b != null)
        b.prev = a;
    else
        back = a;
} 

And added these changes to the partition method:

private Node<T> partition(Node<T> begin, Node<T> end, Comparator<T> comparator) {
    var pivot = end.data;

    var i = begin.prev;
    Node<T> next;

    for (var j = begin; j != end; j = next) {
        next = j.next;
        if (comparator.compare(j.data, pivot) < 0) {
            i = (i == null) ? begin : i.next;

            //swapData(i, j);
            swapNodes(i, j);
            i = j;
        }
    }

    i = (i == null) ? begin : i.next;
    //swapData(i, end);
    swapNodes(i, end);

    //return i;
    return end;
}

At this point the code is not working correctly and I can't figure out why. What am I missing?

Edit:

The expected output is the sorted input which in the second case it is not.

Example:

Initial :[2, 9, 8, 3, 6, 2, 4, 1, 7, 6]
Expected:[1, 2, 2, 3, 4, 6, 6, 7, 8, 9]
Actual:  [1, 3, 2, 4, 2, 6, 9, 6, 7, 8]

A working example can be found here: https://ideone.com/UQrzY1

Edit2:

Provided a shorter example and input/output.

Answer 1

There is a reason the bug in the "swap-nodes variant" is hard to pin down:
You don't support debugging. Make it a habit to have classes provide a basic toString():

/** doubly linked list node */
static class Node<T> {
    …
   /** constructs a <code>Node</code> given data, next & prev */
    public Node(T d, Node…
    
    @Override
    public String toString() {
        return String.valueOf(data);
    }
}

It's a bit more complicated with the lists -

    /** Append string representations of <code>node</code>s 
     * <code>data</code> to <code>head</code>, following 
     * <code>next</code>s til <code>end</code> (or <code>null</code>)
     * (inclusive)
     */
    Appendable append(Node<T> node, final Node<T> end,
        CharSequence separator, Appendable head) {
        try {
            while (end != node) {
                head.append(String.valueOf(node));
                if (null == node
                    || null == (node = node.next) && null == end)
                    return head;
                head.append(separator);
            }
            head.append(String.valueOf(node));
        } catch (IOException e) {
            e.printStackTrace();
        }
        return head;
    }

    @Override
    public String toString() {
        return ((StringBuilder)append(front, null, ", ",
            new StringBuilder("["))).append(']').toString();
    }

    void bug(String label, Node<T> node, final Node<T> end) {
        System.out.append(((StringBuilder)append(node, end, ", ",
            new StringBuilder(label).append('('))).append(")\n"));
    }
    String verbose(Node<T> n) {
        return "+" + n.prev + "<-" + n + "->" + n.next;
    }
    
    private void quickSort(Node<T> begin, Node<T> end, Comparator<T> comparator) {
        bug("quicksort", begin, end);
        if (end != null && begin != end && begin != end.next) {
            Node<T> temp = partition(begin, end, comparator);
            System.out.println("begin: " + begin + ", temp: "
                + verbose(temp) + ", temp == end: " + (temp == end));
            quickSort(begin, temp.prev, comparator);
            bug("between", begin, temp.prev);
            quickSort(temp.next, end, comparator);
        }
    }

Using above intrusive debugging, you can see that end doesn't stay the end of the right part - how would it being picked the pivot element in a Lomuto partition.
Nor does begin stay the beginning of the left part - you'd seem to need successor of begin's predecessor and predecessor of end's successor respectively.
Ensuing a wagonload of special cases without sentinel nodes before and after the list.