Reputation: 11
I am trying to implement a timsort algorithm in Python. I was wondering how I could implement the following into my algorithm:
def calcMinRun(n):
r = 0
while n >= 32:
r |= n & 1
n >>= 1
return n + r
def insertion(arr, left, right):
for i in range(left + 1, right + 1):
j = i
while j > left and arr[j] < arr[j - 1]:
arr[j], arr[j - 1] = arr[j - 1], arr[j]
j -= 1
def timSort(arr):
n = len(arr)
minRun = calcMinRun(n)
for start in range(0, n, minRun):
end = min(start + minRun - 1, n - 1)
insertion(arr, start, end)
size = minRun
while size < n:
for left in range(0, n, 2 * size):
mid = min(n - 1, left + size - 1)
right = min((left + 2 * size - 1), (n - 1))
if mid < right:
merge(arr, left, mid, right)
size = 2 * size
return arr
def merge(arr, start, mid, end):
start2 = mid + 1
if arr[mid] <= arr[start2]:
return
while start <= mid and start2 <= end:
if arr[start] <= arr[start2]:
start += 1
else:
value = arr[start2]
index = start2
while index != start:
arr[index] = arr[index - 1]
index -= 1
arr[start] = value
start += 1
mid += 1
start2 += 1
Any help would be appreciated!
Upvotes: 1
Views: 57