CODEWITHSUNDEEP
algorithmsortingmergetime-complexity
Satish Chauhan
Satish Chauhan

Reputation: 116

How can we improve merge sorting algorithm?

I am trying to modify merge sorting algorithm. As per my modification it looks like it reduce best case and wort case time complexity from O(nlogn) to O (n). I am still working for average time complexity.

As we know that merge sort algorithm is based on divided and conquer method.

Best Case:

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

  1. As per merge sort logic we have to split given input into two half group. Continue half process till group size get length 1.

  2. After split we go for merge process in fact if number are already sorted. I think we can remove merging process by adding simple one condition

Condition: Check if left half of nth element is less then right half of first element. If yes then it is already in sorted no need to compare two half.

eg:

L: 1 2 3 4 5       R: 6 7 8 9 10                
if L[4] < R[0]:
    #two half are already 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 we have to split given input into two half group. Continue half process till group size get length 1.
  2. It split two half alway be in sort order. In merge process we just reorder two half element by linear process. If you look at reverse sort left and right half. You will find that left group is greater then right group. So here we just need to swap left group to right group.

Condition: Check if left half of 1th element is greater then right half of nth element. If yes then it swap left group and right group

eg:

L: 6 7 8 9 10       R: 1 2 3 4 5    
if L[0] > R[4]:
    #two half are already in sorted order
    # swap left and right group value as it is
else
    #run merge algorithm

If you have any idea please let us know. Thanks In Advance :).

Upvotes: 0

Views: 2678

Answers (1)

Cătălin Fr&#226;ncu
Cătălin Fr&#226;ncu

Reputation: 1199

The worst-case complexity is not really O(n), it is still O(n log n). If you use an array-type structure, then swapping the left and right halves takes O(n) time, because you need to move n elements around. If you try using a linked list-type structure, then swapping can be done in O(1), but then finding the midpoint takes O(n).

Either way, the recurrence formula is still T(n) = 2 T(n / 2) + O(n), which solves to T(n) = O(n log n) according to the master theorem.

Upvotes: 2

Related Questions