Sorting algorithms (BS, SS, IS, MS, QS)

def BubbleSort(list):
    for i in xrange(len(list)-2, -1, -1):
        for j in xrange(i + 1):
            if list[j] > list[j+1]:
                list[j], list[j+1] = list[j+1], list[j]

    return list


def SelectionSort(list):
    for i in xrange(0, len(list) - 1):
        position = i
        for j  in xrange(i+1, len(list)):
            if list[position] > list[j]:
                position  = j

        if position != i:
            t = list[i]
            list[i] = list[position]
            list[position] = t

    return list


def InsertionSort(list):
    for i in xrange(1, len(list), 1):
        element = list[i]
        j = i

        while j > 0 and element < list[j-1]:
            list[j] = list[j-1]
            j = j - 1

        list[j] = element

    return list


def MergeLists(left, right):
    result = []

    while len(left) > 0 or len(right) > 0:
        if len(left) > 0 and len(right) > 0:
            if left[0] < right[0]:
                result.append(left[0])
                left = left[1:]
            else:
                result.append(right[0])
                right = right[1:]
        elif len(left) > 0:
            result.append(left[0])
            left = left[1:]
        else:
            result.append(right[0])
            right = right[1:]

    return result

def MergeSort(list):
    if len(list) <= 1:
        return list

    leftList = []
    rightList = []

    middle = len(list)//2

    for i in xrange(middle):
        leftList.append(list[i])

    for i in xrange(middle, len(list), 1):
        rightList.append(list[i])

    leftList  = MergeSort(leftList)
    rightList = MergeSort(rightList)

    return MergeLists(leftList, rightList)


def QuickSort(list, left, right):
    if left < right:
        pivot = list[(left + right)//2]
        list[(left + right)//2], list[right] = list[right], list[(left + right)//2]

        start = left

        for i in xrange (left, right, 1):
            if list[i] <= pivot:
                list[start], list[i] = list[i], list[start]
                start += 1

        list[start], list[right] = list[right], list[start]

        QuickSort(list, left, start - 1)
        QuickSort(list, start + 1, right)

    return  list