# Array sort algorithms in Python

## Definitions

### What is stable sorting?

A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.

### What is in-place sorting?

An in-place sorting algorithm uses constant extra space even for producing the output (modifies the given array only). For example, Insertion Sort and Selection Sorts are in-place sorting algorithms and a typical implementation of Merge Sort is not in-place.

### What are Internal and External Sorting?

When all data that needs to be sorted cannot be placed in-memory at a time, the sorting is called external sorting. External Sorting is used for massive amount of data. Merge Sort and its variations are typically used for external sorting. Some external storage like hard-disk, CD, etc is used for external storage.

When all data is placed in-memory, then sorting is called internal sorting.

## Insertion Sort

Insertion sort is a simple sorting algorithm that is relatively efficient for small lists and mostly sorted lists, and is often used as part of more sophisticated algorithms.

Class | Sorting algorithm |
---|---|

Data structure | Array |

Worst-case performance | О(n2) comparisons, swaps |

Best-case performance | O(n) comparisons, O(1) swaps |

Average performance | О(n2) comparisons, swaps |

Worst-case space complexity | О(n) total, O(1) auxiliary |

Boundary Cases | Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted. |

Algorithmic Paradigm | Incremental Approach |

Sorting In Place | Yes |

Stable | Yes |

Online | Yes |

Uses | Insertion sort is used when number of elements is small. It can also be useful when input array is almost sorted, only few elements are misplaced in complete big array. |

```
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
if __name__ == '__main__':
test1 = insertion_sort([12, 11, 13, 5, 6])
if not test1 == [5, 6, 11, 12, 13]: raise AssertionError
```

## Merge sort

Class | Sorting algorithm |
---|---|

Data | structure Array |

Worst-case performance | O(n log n) |

Best-case performance | O(n log n) typical, O(n) natural variant |

Average performance | O(n log n) |

Worst-case space complexity | О(n) total, O(n) auxiliary |

Algorithmic Paradigm | Divide and Conquer |

Sorting In Place | No in a typical implementation |

Stable | Yes |

```
def merge(l, r):
i = 0
j = 0
s = []
while i < len(l) and j < len(r):
if (l[i] <= r[j]):
s.append(l[i])
i += 1
else:
s.append(r[j])
j += 1
while i < len(l):
s.append(l[i])
i += 1
while j < len(r):
s.append(r[j])
j += 1
return s
def merge_sort(arr):
ln = len(arr)
if ln > 1:
m = int(ln / 2)
l = arr[ : m]
r = arr[m: ]
ls = merge_sort(l)
rs = merge_sort(r)
return merge(ls, rs)
else:
return arr
if __name__ == '__main__':
test0 = merge_sort([7, 89, 60])
if not test0 == [7, 60, 89]: raise AssertionError
test1 = merge_sort([12, 11, 13, 5, 6])
if not test1 == [5, 6, 11, 12, 13]: raise AssertionError
test2 = merge_sort([12, 11, 13, 5, 6, 13])
if not test2 == [5, 6, 11, 12, 13, 13]: raise AssertionError
test3 = merge_sort([12, 5, 11, 13, 5, 6, 13])
if not test3 == [5, 5, 6, 11, 12, 13, 13]: raise AssertionError
```

## Quick Sort

Class | Sorting algorithm | |
---|---|---|

Worst-case performance | O(n2) | |

Best-case performance | O(n log n) (simple partition) | or O(n) (three-way partition and equal keys) |

Average performance | O(n log n) | |

Worst-case space complexity | O(n) auxiliary (naive) | O(log n) auxiliary (Sedgewick 1978) |

```
def partition(array, begin, end):
pivot = begin
for i in range(begin + 1, end + 1):
if array[i] <= array[begin]:
pivot += 1
array[i], array[pivot] = array[pivot], array[i]
array[pivot], array[begin] = array[begin], array[pivot]
return pivot
def quick_sort(array, begin=0, end=None):
if end is None:
end = len(array) - 1
def _quicksort(array, begin, end):
if begin >= end:
return
pivot = partition(array, begin, end)
_quicksort(array, begin, pivot - 1)
_quicksort(array, pivot + 1, end)
return array
return _quicksort(array, begin, end)
if __name__ == '__main__':
test0 = quick_sort([7, 89, 60])
print('test0', test0)
if test0 != [7, 60, 89]: raise AssertionError
test1 = quick_sort([12, 11, 13, 5, 6])
print('test1', test1)
if test1 != [5, 6, 11, 12, 13]: raise AssertionError
test2 = quick_sort([12, 11, 13, 5, 6, 13])
print('test2', test2)
if test2 != [5, 6, 11, 12, 13, 13]: raise AssertionError
test3 = quick_sort([12, 5, 11, 13, 5, 6, 13])
print('test3', test3)
if test3 != [5, 5, 6, 11, 12, 13, 13]: raise AssertionError
```