# Merge sort and linked list implementation

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 implementation
• any information on why the implementation is so inefficient

public 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) {

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) {
right.next();
}
else {
left.next();
}
}

while (left.previousIndex() + 1 >= low) {
}
while (right.previousIndex() + 1 > middle) {
}

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 tail;
private int size;

head = new Node(null, null, null);
tail = new Node(null, head, null);
size = 0;
}

public T removeFirst() {
if (size == 0) {
throw new IllegalStateException("Empty list");
}
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");
}
}

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("[");
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 addAfter(T element, T target) {
Node targetNode = findNode(target);
if (targetNode == null) {
throw new NoSuchElementException("Element " + target + " not in list");
}
}

public void add(int index, T element) {
if (index > size || index < 0) {
throw new IndexOutOfBoundsException(index + " is out of bounds");
}
else if (index == 0) {
return;
}
else if (index == size) {
}

else {
Node targetNode = findNode(index);
}
}

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 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;
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() {
}

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() {
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() {
}

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();
}

if (last == null) {
}
else if (last.getNext() == current) {
}
else if (current.getNext() == 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) {
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) {
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;
}
for (int i = 0; i < index; i++) {
currentNode = currentNode.getNext();
}
return currentNode;
}

}

• 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 inscreases your runtime. I don't see any other reason for the O(n^2) runtime. Take a look at the classical merge sort for linkedlists.
– user66619
Dec 18, 2016 at 18:23

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.