Big O notation for Sorting Algorithm I am interested to know whether the time complexity of following algorithm is  $O(n^2)$ or $O(n\log n)$.

Here is the implementation:

public class HelloWorld
{

 public static void main(String[] args)
 {

    Hello hw = new Hello();
    int[] n = {2,3,4,52,5,63,0,664,2,2,56,68,8};
    hw.sortUsingDLLWODup(n);
 }
}

public class Node
{
   public int value;
public Node next;
public Node prev;
public Node(int v) {
    value = v;
}
}

public class Hello
{

public void sortUsingDLLWODup(int[] n) {

int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0;i&lt;n.length;i++) {
if(max&lt;n[i])max = n[i];
if(min&gt;n[i])min = n[i];
}

Node root = new Node(min);
Node end = new Node(max);
root.next = end;
end.prev = root;

for(int i = 0;i&lt;n.length;i++)
{
    Node current = root;
    while(n[i]&gt;current.value &amp;&amp; current!=null) {
        current = current.next;
    }
    if(current!=null&amp;&amp;current.value&gt;n[i]) {
        Node temp = current.prev;
        Node newNode = new Node(n[i]);
        temp.next = newNode;
        newNode.prev = temp;
        newNode.next = current;
        current.prev = newNode;
    }
}
Node test = root;
while(test!=null){

System.out.println(test.value);
test = test.next;
  }
}    
}
You will have $O(n^2)$ in worst case. Actually what you do is really close to insertion sort. Worst case is attained when you got the array in decreasing order. 

\begin{align}
T(n) &amp;= T(n-1) + n\\
&amp;=T(n-2) + n-1 + n \\
&amp;= \vdots \\
&amp;=T(n-k) + \sum_{i=0}^k (n - i)
\end{align}
Algorithm terminates at $k = n$, i.e. we shall get
$$T(n) = T(0) + \sum_{i=0}^n (n - i)$$
where $T(0) = O(1)$. So, upon a change of variable, we get
 $$T(n) = \sum_{i=0}^n i = \frac{n(n+1)}{2} = O(n^2)$$