Patterns & Code

import random
import traceback

def stringList(sourceList):
    return ",".join([str(x) for x in sourceList])

def quicksort(L):
    """Quicksort recurcively sorts a list by:
    
       - If the list is one element long, it returns that list as sorted.

       - Else:
           - Pick a random value in the list as a "pivot"
           - Divide the remainder of the list into 2 sublists
             - one contains all elements less than the pivot value
             - the other contains all the elements greater than or equal to
               the pivot value
           - Recurcively calls Quicksort for each sublist, in a recursion tree

                        List[1..n], pivot at a
                                   !
                            !------!-----!
                            !            !
             Sub-List[1..a-1]            Sub-List[a+1..n]

           - When the recursive calls return, reassemble the "less than" list,
             the pivot, and the "greater than" list.
      
       - The strategy ensures that for any two sub-lists on the same level in 
         the recursion tree, all elements in the "left most" list are smaller
         than the elements in the "right most" list, even if the sub-lists 
         themselves are unsorted. 

       Note: This is NOT an in place partitioning implementation of the algorithm,
             and thus uses O(n) extra storage space, as all sub-lists are copied.
12345678901234567890123456789012345678901234567890123456789012345678901234567890
"""

    retVal = L

    print "Sorting: [%s]" % stringList(L)

    if len(L) > 1:

        pivot = random.randrange(len(L))

        print "Selecting %d at position %d as the pivot." % (L[pivot],pivot)

        elements = L[:pivot]+L[pivot+1:]
        left  = [element for element in elements if element < L[pivot]]
        right =[element for element in elements if element >= L[pivot]]

        print "Sorted the sublists into [%s] and [%s]" % (stringList(left),
            stringList(right))

        # Note: Recurcive calling of Quicksort would normally be a single
        # statement: retVal = quicksort(left)+[L[pivot]]+quicksort(right)
        #
        # It has been broken down into multiple statement to intersperse
        # illustrative messages.

        retVal = quicksort(left)
        retVal += [L[pivot]]

        print "appending pivot value %d to list: [%s]" %\
           (L[pivot],stringList(retVal))

        tempVal = quicksort(right)

        print "Concatenating sorted lists [%s] and [%s]." %\
           (stringList(retVal),stringList(tempVal))

        retVal += tempVal

    if retVal == L:
      print "[%s] is already in sorted order." % stringList(L)

    print "Returning sorted list [%s]." % stringList(retVal)

    return retVal

def main():
    try:

        shuffledList = [6,1,5,2,4,3]
        sortedList = quicksort(shuffledList)

        print "Before: [%s]" % stringList(shuffledList)
        print "After: [%s]" % stringList(sortedList)

    except Exception as e:
        print e
        print traceback.format_exc()

if __name__ == "__main__":
  main()

# Results
#
# Sorting: [6,1,5,2,4,3]
# Selecting 2 at position 3 as the pivot.
# Sorted the sublists into [1] and [6,5,4,3]
# Sorting: [1]
# [1] is already in sorted order.
# Returning sorted list [1].
# appending pivot value 2 to list: [1,2]
# Sorting: [6,5,4,3]
# Selecting 4 at position 2 as the pivot.
# Sorted the sublists into [3] and [6,5]
# Sorting: [3]
# [3] is already in sorted order.
# Returning sorted list [3].
# appending pivot value 4 to list: [3,4]
# Sorting: [6,5]
# Selecting 5 at position 1 as the pivot.
# Sorted the sublists into [] and [6]
# Sorting: []
# [] is already in sorted order.
# Returning sorted list [].
# appending pivot value 5 to list: [5]
# Sorting: [6]
# [6] is already in sorted order.
# Returning sorted list [6].
# Concatenating sorted lists [5] and [6].
# Returning sorted list [5,6].
# Concatenating sorted lists [3,4] and [5,6].
# Returning sorted list [3,4,5,6].
# Concatenating sorted lists [1,2] and [3,4,5,6].
# Returning sorted list [1,2,3,4,5,6].
#
# Before: [6,1,5,2,4,3]
# After: [1,2,3,4,5,6]
#