-
Notifications
You must be signed in to change notification settings - Fork 166
/
TimSort.py
94 lines (73 loc) · 2.37 KB
/
TimSort.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
# Python3 program to perform TimSort.
RUN = 32
# This function sorts array from left index to
# to right index which is of size atmost RUN
def insertion_sort(arr, left, right):
for i in range(left + 1, right + 1):
temp = arr[i]
j = i - 1
while arr[j] > temp and j >= left:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = temp
# merge function merges the sorted runs
def merge(arr, l, m, r):
# original array is broken in two parts
# left and right array
len1, len2 = m - l + 1, r - m
left, right = [], []
for i in range(0, len1):
left.append(arr[l + i])
for i in range(0, len2):
right.append(arr[m + 1 + i])
i, j, k = 0, 0, l
# after comparing, we merge those two array
# in larger sub array
while i < len1 and j < len2:
if left[i] <= right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1
# copy remaining elements of left, if any
while i < len1:
arr[k] = left[i]
k += 1
i += 1
# copy remaining element of right, if any
while j < len2:
arr[k] = right[j]
k += 1
j += 1
# iterative Timsort function to sort the
# array[0...n-1] (similar to merge sort)
def tim_sort(arr):
n = len(arr)
# Sort individual subarrays of size RUN
for i in range(0, n, RUN):
insertion_sort(arr, i, min((i + 31), (n - 1)))
# start merging from size RUN (or 32). It will merge
# to form size 64, then 128, 256 and so on ....
size = RUN
while size < n:
# pick starting point of left sub array. We
# are going to merge arr[left..left+size-1]
# and arr[left+size, left+2*size-1]
# After every merge, we increase left by 2*size
for left in range(0, n, 2 * size):
# find ending point of left sub array
# mid+1 is starting point of right sub array
mid = left + size - 1
right = min((left + 2 * size - 1), (n - 1))
# merge sub array arr[left.....mid] &
# arr[mid+1....right]
merge(arr, left, mid, right)
size = 2 * size
# Driver program to test above function
if __name__ == "__main__":
arr = [5, 21, 7, 23, 19]
print("Given Array is:", arr)
tim_sort(arr)
print("After Sorting Array is:", arr)