# Sorting algorithms in Python

Here is a list of sorting algorithms in python

## Bubble sort in Python

Bubble sort derives its name from the fact that the bigger element in the array is bubbled up on each iteration.

``````def bubble_sort(array):
n = len(array)

for i in range(n):

for j in range(n - i - 1):
if array[j] > array[j + 1]:
array[j], array[j + 1] = array[j + 1], array[j]

# you had to swap two elements, set the `already_sorted` flag to `False` so the algorithm can keep going

# If there were no swaps during the last iteration, the array is sorted
break

return array
``````

## Insertion sort in Python

This is an algorithm that inserts an unsorted element at a suitable array index in each iteration. Here is how you can implement it using Python.

``````def insertion_sort(array):
n = len(array)

for i in range(1, n):
# This is the element we want to insert at a right place
key_item = array[i]
j = i - 1

while j >= 0 and array[j] > key_item:
array[j + 1] = array[j]
j -= 1

array[j + 1] = key_item

return array
``````

## Merge Sort in Python

This is a divide and conquer sorting algorithm. Merge sort continuously cuts an array into sub-arrays and then merges them at the end.Here is how it's implemented in python.

``````def merge(left, right):

if len(left) == 0:
return right

if len(right) == 0:
return left

result = []
index_left = index_right = 0

while len(result) < len(left) + len(right):

if left[index_left] <= right[index_right]:
result.append(left[index_left])
index_left += 1
else:
result.append(right[index_right])
index_right += 1

if index_right == len(right):
result += left[index_left:]
break

if index_left == len(left):
result += right[index_right:]
break

return result
``````

## Quick Sort Algorithm

It also applies the divide and conquer strategy. It divides the unsorted array into two arrays, one with few elements and the other with more elements. The subarrays are then sorted recursively. Here is how it is implemented in python:

``````from random import randint

def quicksort(array):

if len(array) < 2:
return array

low, same, high = [], [], []

pivot = array[randint(0, len(array) - 1)]

for item in array:

if item < pivot:
low.append(item)
elif item == pivot:
same.append(item)
elif item > pivot:
high.append(item)

return quicksort(low) + same + quicksort(high)``````