#!/usr/bin/python
# -*- coding: iso-8859-15 -*-
# bubble-sort ("divide-and-conquer")
# written by spirit

import random;

##### functions #####

def dqsort(ulist):
    """sorts the list it is given and returns the sorted list"""
    if(len(ulist) <= 1):
        return ulist 
    else:
        # define (by chance) a place where the list will be split (pivot element) 
        seperator_index = random.randint(0,len(ulist) - 1)
        # value of pivot element
        seperator = ulist[seperator_index]
        
        leftpart = []
        rightpart = []
        
        for i in range(0, len(ulist)):
            # all elements smaller than pivot element are placed in the left part
            if(i != seperator_index and ulist[i] < seperator):
                leftpart.append(ulist[i])
            
            # the rest goes in the right part
            if(i != seperator_index and ulist[i] >= seperator):
                rightpart.append(ulist[i])
        
        # do the same stuff over and over again (until the lists consist of 2 elements only)
        leftpart = dqsort(leftpart)
        rightpart = dqsort(rightpart)
        
        # build output list - this is ugly but works :-x
        erg = leftpart                       # grab left part...
        erg.append(ulist[seperator_index])   # ...append seperator... 
        for i in range(len(rightpart)):      # ...and the right part
            erg.append(rightpart[i])
        
        return erg
        
##### here we go ######

print "\n\nsort (devide-and-conquer)"
print "----------------------------------"

# the list  we want to sort
LU = [ 53, 7, 4, 20, 23, 23, -10, 1, 100, 93, 8, 2, 5, 77, 111, 63, -1, 42, 10, 30, 40 ]
print "list : ", LU

# just do it
print "sorted list : ", dqsort(LU)