Sorting Algorithms in Python

Below are some popular sorting algorithms implemented in Python.

#!/usr/bin/env python

class BubbleSort(object):
    @staticmethod
    def sort(l):
        new_list = list(l)
        while True:
            swapped = False
            for i in xrange(0, len(new_list)-1):
                if new_list[i] > new_list[i+1]:
                    new_list[i], new_list[i+1] = new_list[i+1], new_list[i]
                    swapped = True
            if not swapped: break
        return new_list

class SelectionSort(object):
    @staticmethod
    def sort(l):
        new_list = list(l)
        for i in xrange(0, len(new_list)):
            min_index = i
            for j in xrange(i, len(new_list)):
                if new_list[j] < new_list[min_index]:
                    min_index = j
            new_list[i], new_list[min_index] = new_list[min_index], new_list[i]
        return new_list

class InsertionSort(object):
    @staticmethod
    def sort(l):
        new_list = list(l)
        for i in xrange(1, len(new_list)):
            j = i
            while j > 0 and new_list[j] < new_list[j-1]:
                new_list[j-1], new_list[j] = new_list[j], new_list[j-1]
                j -= 1
        return new_list

class ShellSort(object):
    @staticmethod
    def sort(l):
        new_list = list(l)
        n = len(l)
        h = 1
        while h < (n/3): h = (3*h) + 1
        while h >= 1:
            for i in xrange(h, n):
                j = i
                while j >=h and new_list[j] < new_list[j-h]:
                    new_list[j], new_list[j-h] = new_list[j-h], new_list[j]
                    j -= h
            h /= 3
        return new_list

class MergeSort(object):
    @staticmethod
    def sort(l):
        new_list = list(l)
        MergeSort.msort(new_list, 0, len(new_list)-1)
        return new_list
    
    @staticmethod
    def msort(l, lo, hi):
        if lo == hi: return
        mi = (lo + hi) / 2
        MergeSort.msort(l, lo, mi)
        MergeSort.msort(l, mi + 1, hi)
        MergeSort.merge(l, lo, mi, hi)
    
    @staticmethod
    def merge(a, lo, mi, hi):
        i = lo
        j = mi + 1
        tmp = list(a)
        hi = hi + 1
        for x in xrange(lo, hi):
            if i > mi:
                a[x] = tmp[j]
                j += 1
            elif j >= hi:
                a[x] = tmp[i]
                i += 1
            elif tmp[i] < tmp[j]:
                a[x] = tmp[i]
                i += 1
            else:
                a[x] = tmp[j]
                j += 1

class QuickSort(object):
    @staticmethod
    def sort(l):
        new_list = list(l)
        import random
        random.shuffle(new_list)
        QuickSort.qsort(new_list, 0, len(new_list)-1)
        return new_list
    
    @staticmethod
    def qsort(l, lo, hi):
        if hi <= lo: return
        j = QuickSort.partition(l, lo, hi)
        QuickSort.qsort(l, lo, j-1)
        QuickSort.qsort(l, j+1, hi)
    
    @staticmethod
    def partition(l, lo, hi):
        i = lo
        j = hi + 1
        v = l[lo]
        while True:
            i += 1
            while l[i] < v:
                if i == hi: break
                i += 1
            j -= 1
            while v < l[j]:
                if j == lo: break
                j -= 1
            if i >= j: break
            l[i], l[j] = l[j], l[i]
        l[lo], l[j] = l[j], l[lo]
        return j

class HeapSort(object):
    @staticmethod
    def sort(l):
        new_list = list(l)
        n = len(new_list)
        # construct a binary heap
        for i in xrange(n/2, 0, -1):
            HeapSort.sink(new_list, i, n)
        # sort down the heap
        for i in xrange(n, 0, -1):
            new_list[i-1], new_list[0] = new_list[0], new_list[i-1]
            HeapSort.sink(new_list, 1, i-1)
        return new_list
    
    @staticmethod
    def sink(l, current_pos, n):
        child_pos = HeapSort.get_child_position(l, current_pos, n)
        if child_pos == -1: return
            
        while l[child_pos-1] > l[current_pos-1]:
            l[child_pos-1], l[current_pos-1] = l[current_pos-1], l[child_pos-1]
            current_pos = child_pos
            child_pos = HeapSort.get_child_position(l, current_pos, n)
            if child_pos == -1: break
            
    @staticmethod
    def get_child_position(l, current_pos, n):
        first_child_pos = 2 * current_pos
        second_child_pos = (2 * current_pos) + 1
        child_pos = -1 # no child
        # no child
        if first_child_pos > n: return child_pos
        # there's only one child
        if second_child_pos > n: child_pos = first_child_pos
        else: # there are two children
            if l[first_child_pos-1] > l[second_child_pos-1]:
                child_pos = first_child_pos
            else:
                child_pos = second_child_pos
        return child_pos
    
if __name__ == "__main__":
   expected_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
   input_list = [9, 3, 6, 5, 7, 1, 8, 10, 2, 4]

   sorted_list = BubbleSort.sort(input_list)
   assert sorted_list == expected_list

   sorted_list = SelectionSort.sort(input_list)
   assert sorted_list == expected_list

   sorted_list = InsertionSort.sort(input_list)
   assert sorted_list == expected_list

   sorted_list = ShellSort.sort(input_list)
   assert sorted_list == expected_list
   
   sorted_list = MergeSort.sort(input_list)
   assert sorted_list == expected_list

   sorted_list = QuickSort.sort(input_list)
   assert sorted_list == expected_list
   
   sorted_list = HeapSort.sort(input_list)
   assert sorted_list == expected_list