Python - Insertion Sort Impl

This article will discuss a simple insertion sort algorithm for python.
See ALL Python postings  |  Insertion Sort By Language Java Scala Go C++ Python Perl

Overview of the Insertion Sort Algorithm
Insertion sort is one of the most natural wayTs of sorting a collection of comparable items.  The reason it is one of the most natural ways is because it is the way most people will sort physical items.   For example each year (about this time) I will sort all 12 of my previous years phone bills, gas bills, etc...  The algorithm used to sort them is to place the first one in stack.  Then the second one is compared to the first one to see if it goes in front of or behind the first one.  The third one is then compared to each if the two sorted items to determine where it fits in.  This procedure continues until all 12 bills are in the pile.  Once all 12 bills are in the pile it is sorted. I happen to sort form oldest to newest, my spouse does it the other way newest to oldest.

Applying this concept to a collection of objects in a computer is fundamentally the same.  The algorithm dictates that one will iterate over a collection of elements in an unsorted list 1 at a time, and place that item into it's correct location in a sorted list.

If the collection of objects to sort is n, insertion sort will take at most $O(n^2)$ operations to perform the sort, it will take on average $\frac{1}{2} O(n^2) = O(n^2)$, and in the best case senario will take $O(n)$ operations.


Questions:  


1.  What would be the initial characteristics of a list that took the worst case order $O(n^2)$ to sort?
2.  What would be the initial characteristics of a list that took the best case order $O(n)$ to sort?


About the Python Solution:
In python this solution relied a bit on creativity.  The solution is clearly not $O(n^2)$,  however it may take a bit to understand why.  The reason lies in the fact that python does not have a linked list that allows insert at a given point in the list.  Therefore, to simulate that behavior, this solution rotates the list until it cat append to the left side of the list, and then rotates back.  This ensures that the order is correct.  What would be the big O of this solution assuming that each rotation is O(n)? Some additional inline comments have been included.

If you have a question about the solution (or feel it should be improved) please leave a comment.  All comments are moderated and posted with your name/Identification so please be professional and straight forward. Python Solution:

#!/opt/python
from collections import deque
import random

dq = deque()
for i in range(20):
    dq.append(random.randrange(1001))

for elem in dq:
    print(elem)

sortedQueue = deque()
j=int(0)
k=int(0)
for elem in dq:


    for sortedElem in sortedQueue :
        if elem>sortedElem:
            sortedQueue.rotate(-j)
            sortedQueue.appendleft(elem)
            sortedQueue.rotate(j)
            k=1+k
            break
        j=j+1
    if (k == 0):
        sortedQueue.append(elem)
    else:
        k=0
    j=0

print (sortedQueue)

Answers: 1.  The best case senario would be order: $O(n)$ 2.  The worst case senario would be order: $O(n^{2})$golang postings