let's comparison of elements in array takes o(n), possible sort array in o(n) when first half elements of array smaller other half?
i think yes make easier sort because elements arent mixed much. take care of first half, smaller one, compare 1 element , sort. same second half. wouldn't work in o(n)?
so you're splitting array 2 pieces, items in first piece less smallest item in second piece. sort individual pieces? sounds suspiciously how quicksort works.
and, no, can't in general sort array in o(n). it's long been known lower bound on comparison sorting o(n log n). see https://en.wikipedia.org/wiki/comparison_sort#number_of_comparisons_required_to_sort_a_list quick overview of why. can detailed references there.
