Sorting algorithms - Sam647254/Programetoj GitHub Wiki

Insertion sort

Best performance: O(n); worst performance: O(n²); space: O(1)

Working principle: Go through the list; at each iteration, insert the next unsorted element into the sorted list so far.

Best performance: O(n²); worst performance: O(n²); space: O(1)

Working principle: Go through the list; at each iteration, find the next element to insert into the sorted list so far.

A commonly used sorting algorithm, usually built into programming languages. Performance: O(n²); space: O(n)

Working principle:

An empty list is sorted.
A list of one element is sorted.
It's easy (i.e. it takes O(n) time) to combine two sorted lists into a single sorted list.
In a merge sort, repeatedly split the list into halves until each half is either empty or has a single element, then merge the sublists.

Another commonly used sorting algorithm. Performance: O(n log n) (usually), O(n²) (rare); space: O(n)

Working principle:

Similar to merge sort, an empty list or a list of one element is sorted.
Choose a pivot element (many selection methods exist) and move it to the middle of the list.
Partition the list around this pivot element; that is, move all of the elements greater than it to its right, and all the elements smaller than it to its left.
Repeat this for each of the halves.

Performance: O(n log n), space O(n)

Working principle: Straightforward; put all the elements into a heap, and then pull them out.