Timsort

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
# Python3 program to perform basic timSort 
MIN_MERGE = 32

def calcMinRun(n): 
  """Returns the minimum length of a 
  run from 23 - 64 so that 
  the len(array)/minrun is less than or 
  equal to a power of 2. 
  e.g. 1=>1, ..., 63=>63, 64=>32, 65=>33, 
  ..., 127=>64, 128=>32, ... 
  """
  r = 0
  while n >= MIN_MERGE: 
    r |= n & 1
    n >>= 1
  return n + r 

# This function sorts array from left index to 
# to right index which is of size atmost RUN 
def insertionSort(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

# 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 timSort(arr): 
  n = len(arr) 
  minRun = calcMinRun(n) 
  
  # Sort individual subarrays of size RUN 
  for start in range(0, n, minRun): 
    end = min(start + minRun - 1, n - 1) 
    insertionSort(arr, start, end) 

  # Start merging from size RUN (or 32). It will merge 
  # to form size 64, then 128, 256 and so on .... 
  size = minRun 
  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 = min(n - 1, 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 = [-2, 7, 15, -14, 0, 15, 0, 
    7, -7, -4, -13, 5, 8, -14, 12] 

  print("Given Array is") 
  print(arr) 

  # Function Call 
  timSort(arr) 

  print("After Sorting Array is") 
  print(arr) 
  # [-14, -14, -13, -7, -4, -2, 0, 0, 
    5, 7, 7, 8, 12, 15, 15]