A sorting algorithm is an algorithm that puts elements of a list in a certain order. - Wikipedia
- pass through the data from one end to the other, swap adjacent elements whenever the first is greater than the last.
- O(n^2) - very slow for large data sets
- seeks to sort a list one element at a time.
- one of the principal advantages of the insertion sort is that it works very efficiently for lists that are nearly sorted initially.
- It can also work on data sets that are constantly being added to.
- e.g. if one wanted to maintain a sorted list of the highest scores achieved in a game, an insertion sort would work well, since new elements would be added to the data as the game was played.
- works recursively. First it divides a data set in half, and sorts each half separately.
- next the first elements from each of the two lists are compared.
- the lesser element is then removed from its list and added to the final result list.
- optimization for nearly sorted lists.
- if the highest element in one list is less than the lowest element in the other half, the the merge steps is unnecessary.
- we create a heap data structure.
- head datastructure: stored in a tree such that all the smallest (or largest) elements is always the root node.
- all data is inserted into a heap, then the root element is removed and stored back into the list.
- efficient sorting algorithm.
- divide the data into two groups of “high” values and “low” values.
- then recursively process the two halves. then reassemble the now sorted list.