algorithms.sorting

Merge Sort

In computer science, merge sort (also commonly spelled mergesort) is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Mergesort is a divide and conquer algorithm that was invented by John von Neumann in 1945.

merge_sort(array)

Sort array via merge sort algorithm

Parameters:array – list of elements to be sorted Returns:Sorted list of elements

Examples

>>> merge_sort([1, -10, 21, 3, 5])
[-10, 1, 3, 5, 21]

Quick Sort

Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. Developed by Tony Hoare in 1959[1] and published in 1961,[2] it is still a commonly used algorithm for sorting. [Wikipedia]

https://en.wikipedia.org/wiki/Quicksort

Average complexity: O(n log n) Worst case: O(n^2)

quick_sort(array, low, high)

Quick Sort function sorts array

Parameters:

• array – list of elements
• low – at starting point low must be = 0
• high – at starting point high must be = len(array)-1

Returns:

sorted array

Return type:

list

Examples

>>> quick_sort([4,  9,  4,  4,  1,  9,  4,  4,  9,  4,  4,  1,  4], 0, 12)
[1, 1, 4, 4, 4, 4, 4, 4, 4, 4, 9, 9, 9]

>>> quick_sort([1, 10, 32, 4.], 0, 3)
[1, 4.0, 10, 32]

switch(array, a, b)