# Day 38/100 Sorting Complexity

Any compare-based sorting algorithm must use at least lg ( N ! ) ~ N lg N compares in the worst-case.

## Mergesort:

Lower bound of complexity for mergesort is NlogN but that depends on the conditions of the input array. If array is partially sorted it will take less time to sort, as we know insertion sort can take linear time if array is partially sorted. Also if there are duplicate keys this decreases the complexity of mergesort. Or when the keys are represented in a different way (digit/character compares instead of key compares for numbers and strings). In these cases, the lower bound does no hold!

## Comparators:

**Comparable** interface helps sort out items in natural order. **Comparator** interface helps sort out using alternate order. Must be total order! (what does this mean??). The reason why one would use a comparator over a comparable is that one can have **multiple ordering **of a given data type whereas comparable only allows **one**. Comparable also affects the original class whereas a comparator is objective, it don’t matter if you black or white it does the same thing for class A and class B.

In Java, one can create a comparator object and pass it into parameter of java’s Arrays.sort() method.

## Stability:

Example: Sort by name, then sort by id. How would one preserve first sort? This is called stability! A **stable sort** preserves position of keys (in this case sorting by name then id would preserve original sort and order keys only if duplication names found). Looking at the previous sorts I’ve come across, insertion and mergesort are stable sorts, shellsort and selection are not!

One can detect is a sorting algorithm is **stable** if after sorting, equal / duplicate values have not changed position relative from original array. An **unstable** algorithm is one where equal/duplicate values have switched places or have moved somewhere else in the array from this original relative positioning.

P.S: As mentioned before mergesort is stable if and only if the implementation of mergesort is stable. To ensure stability, take from left array when items are similar.

Now time to get onto the ungraded mergesort questions!