Quick sort, and Insert sort, Bubble sort, Merge sort algorithms

sort_algorithms.py

#!/usr/bin/env python

# Using a pivot
# Place value lower than pivot to the left, greater to the right
# Sort left and right recursively
def quick_sort(arr):
    less, equal, greater = [], [], []
    if len(arr) > 1:
        pivot = arr[0]

        for x in arr:
            if x < pivot:
                less.append(x)
            elif x > pivot:
                greater.append(x)
            else:
                equal.append(x)
        return quick_sort(less) + equal + quick_sort(greater)
    return arr

# Loop through each value
# Find the where to insert the value in the array from the previous indexes
# Shift right the array between the insert index and the index of the value
def insertion_sort(arr):
    for i in range(1, len(arr)):
        j = i
        while j > 0 and arr[j-1] > arr[j]:
            arr[j], arr[j-1] = arr[j-1], arr[j]
            j -= 1

    return arr

# Loop n time
# Loop through each n first value
# Compare values two by two and swap them if the left value is greater, this must place the greatest value to the end
# Decrement n (we know that the greatest value is placed at the end already)
def bubble_sort(arr):
    for n in range(len(arr), 0, -1):
        for i in range(1, n):
            if arr[i - 1] > arr[i]:
                arr[i - 1], arr[i] = arr[i], arr[i - 1]
    return arr


# Sort recursively by splitting the array in half
# Merge the sorted array two by two and return a sorted array
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    middle = len(arr) // 2
    left = merge_sort(arr[:middle])
    right = merge_sort(arr[middle:])

    return _merge(left, right)

def _merge(left, right):
    result, left_idx, right_idx = [], 0, 0

    while left_idx < len(left) and right_idx < len(right):
        if left[left_idx] <= right[right_idx]:
            result.append(left[left_idx])
            left_idx += 1
        else:
            result.append(right[right_idx])
            right_idx += 1

    # consume left-overs from left or right
    if left:
        result.extend(left[left_idx:])
    if right:
        result.extend(right[right_idx:])
    return result

if __name__ == '__main__':
    print merge_sort([8, 9, 8, 1, 11, 13, 1, 0, -7, 8])