Sorting Algorithm Complexities | Java Fresher Interview

I'd group them. The simple comparison sorts, bubble, insertion, and selection, are all O of n squared on average, so they're only practical for tiny inputs or nearly-sorted data, where insertion sort in particular is close to linear. The efficient comparison sorts are O of n log n. Merge sort is O of n log n guaranteed, it's stable, but it needs O of n extra space. Heap sort is also O of n log n guaranteed and it's in place, but it's not stable. Quicksort is the interesting one: it's O of n log n on average and in place, but its worst case is O of n squared, which happens with bad pivot choices, classically on already-sorted input with a naive pivot. A key fact I'd state is that no comparison-based sort can do better than O of n log n in the worst case; that's a proven lower bound, because comparisons can only extract so much information. Non-comparison sorts like counting sort and radix sort get around that by using the values themselves as indices rather than comparing, so they can run in O of n plus k, where k is the range of keys, but they only help when that range is small. Finally, I'd mention what Java actually uses, because it shows practical knowledge: Arrays dot sort uses a dual-pivot quicksort for primitive arrays, and TimSort, which is a hybrid of merge and insertion sort, for object arrays. The reason for the split is stability, primitives don't need it, but objects sorted by a key do.