I implemented merge sort with my own linked list for a school project. I was not allowed to use anything but the methods you see in the list. It seems to work properly, however, when running the provided testbed, I am told that the implementation is likely \$O(n^2)\$.I've looked for a long time trying to find where my implementation is \$O(n^2)\$ but have had no luck. I would appreciate:any input on the quality of the implementationany information on why the implementation is so inefficientpublic class Sort {public static <T extends Comparable<T>> void sort(IUListWithListIterator<T> list) {            _sort(list, 0, list.size() - 1);        }    public static <T extends Comparable<T>> void _sort(IUListWithListIterator<T> list, int low, int high) {        if (low < high) {            int middle = (low + high) / 2;            _sort(list, low, middle);            _sort(list, middle + 1, high);            merge(list, low, middle, high);        }    }    private static <T extends Comparable<T>> void merge(IUListWithListIterator<T> list, int low, int middle, int high) {        IUListWithListIterator<T> temp = new IUDoubleLinkedList<T>();        ListIterator<T> left = list.listIterator(middle);        ListIterator<T> right = list.listIterator(high);        while (left.previousIndex() + 1 >= low && right.previousIndex() + 1 > middle) {            T l = left.previous();            T r = right.previous();            if (l.compareTo(r) > 0) {                temp.addToFront(l);                right.next();            }            else {                temp.addToFront(r);                left.next();            }        }        while (left.previousIndex() + 1 >= low) {            temp.addToFront(left.previous());        }        while (right.previousIndex() + 1 > middle) {            temp.addToFront(right.previous());        }        ListIterator<T> tempIter = temp.listIterator();        left.next();        while(tempIter.hasNext()) {            left.set(tempIter.next());            left.next();        }    }}import java.util.Iterator;import java.util.ListIterator;import java.util.NoSuchElementException;public class IUDoubleLinkedList<T> implements IndexedUnorderedList<T>, IUListWithListIterator<T> {private Node head;private Node tail;private int size;public IUDoubleLinkedList() {    head = new Node(null, null, null);    tail = new Node(null, head, null);    head.setNext(tail);    size = 0;}public T removeFirst() {    if (size == 0) {        throw new IllegalStateException(Empty list);    }    Node first = head.getNext();    removeNode(first);    return first.getData();}public T removeLast() {    if (size == 0) {        throw new IllegalStateException(Empty list);    }    Node last = tail.getPrev();    removeNode(last);    return last.getData();}public T remove(T element) {    Node target = findNode(element);    if (target == null) {        throw new NoSuchElementException(Element  + element +  not in list);    }    removeNode(target);    return target.getData();}public T first() {    if (size == 0) {        throw new IllegalStateException(Empty list);    }    return head.getNext().getData();}public T last() {    if (size == 0) {        throw new IllegalStateException(Empty list);    }    return tail.getPrev().getData();}public boolean contains(T target) {    Node found = findNode(target);    return found == null ? false : true;}public boolean isEmpty() {    return size == 0;}public int size() {    return size;}public String toString() {    StringBuilder b = new StringBuilder();    if (size == 0) {        b.append([]);    }    else {        b.append([);        Node currentNode = head.getNext();        while (currentNode != tail) {            b.append(currentNode.getData().toString() + , );            currentNode = currentNode.getNext();        }        if (b.length() > 3) {            b = new StringBuilder(b.substring(0, b.length() - 2));        }        b.append(]);    }    return b.toString();}public void addToFront(T element) {    addNode(new Node(element), head, head.getNext());       }public void addToRear(T element) {    addNode(new Node(element), tail.getPrev(), tail);       }public void addAfter(T element, T target) {    Node targetNode = findNode(target);    if (targetNode == null) {        throw new NoSuchElementException(Element  + target +  not in list);    }    addNode(new Node(element), targetNode, targetNode.getNext());   }public void add(int index, T element) {    if (index > size || index < 0) {        throw new IndexOutOfBoundsException(index +  is out of bounds);    }    else if (index == 0) {        addToFront(element);        return;    }    else if (index == size) {        addToRear(element);    }    else {        Node targetNode = findNode(index);        addNode(new Node(element), targetNode.getPrev(), targetNode);    }}public void set(int index, T element) {    if (index >= size || index < 0) {        throw new IndexOutOfBoundsException(index +  is out of bounds);    }    Node setNode = findNode(index);    Node newNode = new Node(element, setNode.getPrev(), setNode.getNext());    setNode.getPrev().setNext(newNode);    setNode.getNext().setPrev(newNode);}public void add(T element) {    addNode(new Node(element), tail.getPrev(), tail);       }public T get(int index) {    if (index >= size || index < 0) {        throw new IndexOutOfBoundsException(index +  is out of bounds);    }    Node target = findNode(index);    return target.getData();}public int indexOf(T element) {    int i = 0;    Node currentNode = head.getNext();    while (currentNode != tail) {        if (currentNode.getData().equals(element)) {            return i;        }        currentNode = currentNode.getNext();        i++;    }    return -1;}public T remove(int index) {    if (index > size - 1 || index < 0) {        throw new IndexOutOfBoundsException(index +  is out of bounds);    }    Node targetNode = findNode(index);    removeNode(targetNode);    return targetNode.getData();}public Iterator<T> iterator() {    return new DLLIterator();}private class DLLIterator implements Iterator<T> {    private Node next;    private DLLIterator() {        next = head.getNext();    }    private DLLIterator(int index) {        next = findNode(index);    }    public boolean hasNext() {        return next != tail;    }    public T next() {        if (!hasNext()) {            throw new NoSuchElementException();        }        next = next.getNext();        return next.getPrev().getData();    }    public void remove() {        removeNode(next.getPrev());    }}public ListIterator<T> listIterator() {    return new DLLListIterator<T>();}public ListIterator<T> listIterator(int startingIndex) {    return new DLLListIterator<T>(startingIndex);}private class DLLListIterator<E> implements ListIterator<T> {    Node current;    Node last;    int index;    private DLLListIterator() {        current = head.getNext();        last = null;        index = 0;    }    private DLLListIterator(int startingIndex) {        current = findNode(startingIndex);        index = startingIndex;    }    public boolean hasNext() {        return current != tail;    }    public T next() {        if (current.getNext() == last) {            current = last.getNext();            index++;            return last.getData();        }        last = current;        current = current.getNext();        index++;        return last.getData();    }    public void remove() {        if (last == null) {            throw new IllegalStateException(can't call remove() before calling next() or previous());        }        removeNode(last);        last = null;        index--;    }    public boolean hasPrevious() {        return current != head;    }    public T previous() {        if (last != null && last.getNext() == current) {            current = last.getPrev();            index--;            return last.getData();        }        last = current;        current = current.getPrev();        index--;        return last.getData();    }    public void add(T element) {        if (last == null) {            addNode(new Node(element), current.getPrev(), current);        }        else if (last.getNext() == current) {            addNode(new Node(element), last, current);        }        else if (current.getNext() == last) {            addNode(new Node(element), current, last);        }        index++;    }    public void set(T element) {        if (last == null) {            throw new IllegalStateException(can't call set(T) before calling next() or previous());        }        last.setData(element);    }    public int nextIndex() {        return index + 1;    }    public int previousIndex() {        return index - 1;    }}private class Node {    private Node prev;    private Node next;    private T data;    public Node(T data, Node before, Node after) {        this.prev = before;        this.next = after;        this.data = data;    }    public Node(T data) {        this.data = data;    }    public Node getPrev() {        return prev;    }    public void setPrev(Node n) {        prev = n;    }    public Node getNext() {        return next;    }    public void setNext(Node n) {        next = n;    }    public T getData() {        return data;    }    public void setData(T d) {        data = d;    }}private void addNode(Node n, Node before, Node after) {    before.setNext(n);    after.setPrev(n);    n.setNext(after);    n.setPrev(before);    size++;}private void removeNode(Node n) {    if (n == head) {        throw new IllegalStateException(Can't remove the head of the list);    }    if (n == tail) {        throw new IllegalStateException(Can't remove the tail of the list);    }    n.getPrev().setNext(n.getNext());    n.getNext().setPrev(n.getPrev());    size--;}private Node findNode(T target) {    Node currentNode = head.getNext();    while (currentNode != tail) {        if (currentNode.getData() == target) {            return currentNode;        }        //System.out.println(currentNode.getData());        currentNode = currentNode.getNext();    }    return null;}private Node findNode(int index) {    if (index > size || index < 0) {        throw new IndexOutOfBoundsException();    }    if (index == size) {        return tail;    }    Node currentNode = head.getNext();    for (int i = 0; i < index; i++) {        currentNode = currentNode.getNext();    }    return currentNode;}}
Merge sort and linked list implementation
java;performance;linked list;mergesort
You are taking an index-based approach to a problem in which there is no use of index at all. In _sort(..), you call list.listIterator(index) every time and it in turn calls findNode(..) which is \$O(n)\$. This dramatically increases your runtime. I don't see any other reason for the overall \$O(n^2)\$ runtime. Take a look at the classical merge sort for linked lists.