Sorting¶
change order of collected elements to whats required.
In Place¶
 Does not use extra space for manipulating the input but may require a small though nonconstant extra space for its operation.
 Usually, this space is O(log n), though sometimes anything in o(n) (Smaller than linear) is allowed.
Stable¶
 Stability is mainly important when we have key value pairs with duplicate keys possible (like people names as keys and their details as values).
 And we wish to sort these objects by keys.
 equivalent elements retain their relative positions.
 need stability when in (key, value) > keys are equal but values have some significance of order.
 Indistinguishable, (integers), all keys are different. > do not need.
 Relative order is maintained in an Unstable Sort > highly unlikely.
 Does not effect performance and takes some extra space, possibly theta(n). > to make unstable algo to stable.
 by changing the key comparison operation so that the comparison of two keys considers position as a factor for objects with equal keys.
External Algo¶
In computing, external memory algorithms or outofcore algorithms are algorithms that are designed to process data that are too large to fit into a computer's main memory at once.
Lower bound for comparison based sorting¶
Input:
 uses comparison operators
 decision trees.
 A decision tree > full binary tree that represents the comparisons between elements that are performed by a particular sorting algorithm operating on an input of a given size.
 tracing a path from the root of the decision tree to a leaf.
 At each internal node, a comparison ai <= aj is made.
 left subtree > ai <= aj.
 right subtree > ai > aj.

When reach leaf, ordering is done.

n! permutations on n > leaves for the sorting algorithm to sort properly.
 x > maximum number
 maximum height of the decison tree_ > x.
 A tree with maximum height x has at most 2^x leaves.
n! <= 2^x
Taking Log on both sides.
log2(n!) <= x
As log2(n!) = Θ(nLogn) => x = Ω(nLog2n)
Hence Heapsort, merge sort > asymptotically optimal comparison sorts.
minimum number of memory writes?¶
Some huge data set is very expensive > EEPROMs or Flash memory > each write reduces the lifespan of the memory.
Selection Sort makes least number of writes (it makes O(n) swaps).
Cycle Sort > zero times > correct position or written one time to its correct position.
Hence Cycle Sort