Day 38/100 Sorting Complexity

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


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!


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.


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!