More efficient merge sort


Joined
May 11, 2022
Messages
50
Reaction score
3
Python:
import random
def mergeSort(N,low,high):
   if low == len(N)-1:
      return
   if high - low == 1:
      if N[high] <N[low]:
         N[high], N[low] = N[low], N[high]
      return
   if high - low == 0:
      return
   mergeSort(N,low,(low+high)//2)
   mergeSort(N,(low+high)//2,high)
   for i in range(low,high):
      j = i
      while j >low and N[j] < N[j-1]:
         N[j], N[j-1] =N[j-1],N[j]
         j -= 1
So this version doesn't require an auxiliary array.
 
Ad

Advertisements

Ad

Advertisements

Joined
May 11, 2022
Messages
50
Reaction score
3
i ran some tests, and the original merge sort is significantly faster. sorry for the incorrect post.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top