How can we improve merge sorting algorithm? -

i trying modify merge sorting algorithm. per modification looks reduce best case , wort case time complexity o(nlogn) o (n). still working average time complexity.

as know merge sort algorithm based on divided , conquer method.

best case:

input: 1 2 3 4 5 6 7 8 9 10

1. as per merge sort logic have split given input 2 half group. continue half process till group size length 1.

2. after split go merge process in fact if number sorted. think can remove merging process adding simple 1 condition

condition: check if left half of nth element less right half of first element. if yes in sorted no need compare 2 half.

eg:

l: 1 2 3 4 5       r: 6 7 8 9 10                 if l[4] < r[0]:     #two half in sorted order else     #run merge algorithm 

wort case:

input: 10 9 8 7 6 5 4 3 2 1

1. as per merge sort logic have split given input 2 half group. continue half process till group size length 1.
2. it split 2 half alway in sort order. in merge process reorder 2 half element linear process. if @ reverse sort left , right half. find left group greater right group. here need swap left group right group.

condition: check if left half of 1th element greater right half of nth element. if yes swap left group , right group

eg:

l: 6 7 8 9 10       r: 1 2 3 4 5     if l[0] > r[4]:     #two half in sorted order     # swap left , right group value else     #run merge algorithm 

if have idea please let know. in advance :).

the worst-case complexity not o(n), still o(n log n). if use array-type structure, swapping left , right halves takes o(n) time, because need move n elements around. if try using linked list-type structure, swapping can done in o(1), finding midpoint takes o(n).

either way, recurrence formula still t(n) = 2 t(n / 2) + o(n), solves t(n) = o(n log n) according the master theorem.