TimSort | Python3 program to perform basic timSort ; Becomes 1 if any 1 bits are shifted off ; This function sorts array from left index to to right index which is of size atmost RUN ; Merge function merges the sorted runs ; original array is broken in two parts left and right array ; after comparing , we merge those two array in larger sub array ; Copy remaining elements of left , if any ; Copy remaining element of right , if any ; Iterative Timsort function to sort the array [ 0. . . n - 1 ] ( similar to merge sort ) ; Sort individual subarrays of size RUN ; Start merging from size RUN ( or 32 ) . It will merge to form size 64 , then 128 , 256 and so on ... . ; 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 ; Find ending point of left sub array mid + 1 is starting point of right sub array ; Merge sub array arr [ left ... . . mid ] & arr [ mid + 1. ... right ] ; Driver program to test above function ; Function Call
MIN_MERGE = 32 NEW_LINE def calcMinRun ( n ) : NEW_LINE INDENT r = 0 NEW_LINE while n >= MIN_MERGE : NEW_LINE INDENT r |= n & 1 NEW_LINE n >>= 1 NEW_LINE DEDENT return n + r NEW_LINE DEDENT def insertionSort ( arr , left , right ) : NEW_LINE INDENT for i in range ( left + 1 , right + 1 ) : NEW_LINE INDENT j = i NEW_LINE while j > left and arr [ j ] < arr [ j - 1 ] : NEW_LINE INDENT arr [ j ] , arr [ j - 1 ] = arr [ j - 1 ] , arr [ j ] NEW_LINE j -= 1 NEW_LINE DEDENT DEDENT DEDENT def merge ( arr , l , m , r ) : NEW_LINE INDENT len1 , len2 = m - l + 1 , r - m NEW_LINE left , right = [ ] , [ ] NEW_LINE for i in range ( 0 , len1 ) : NEW_LINE INDENT left . append ( arr [ l + i ] ) NEW_LINE DEDENT for i in range ( 0 , len2 ) : NEW_LINE INDENT right . append ( arr [ m + 1 + i ] ) NEW_LINE DEDENT i , j , k = 0 , 0 , l NEW_LINE while i < len1 and j < len2 : NEW_LINE INDENT if left [ i ] <= right [ j ] : NEW_LINE INDENT arr [ k ] = left [ i ] NEW_LINE i += 1 NEW_LINE DEDENT else : NEW_LINE INDENT arr [ k ] = right [ j ] NEW_LINE j += 1 NEW_LINE DEDENT k += 1 NEW_LINE DEDENT while i < len1 : NEW_LINE INDENT arr [ k ] = left [ i ] NEW_LINE k += 1 NEW_LINE i += 1 NEW_LINE DEDENT while j < len2 : NEW_LINE INDENT arr [ k ] = right [ j ] NEW_LINE k += 1 NEW_LINE j += 1 NEW_LINE DEDENT DEDENT def timSort ( arr ) : NEW_LINE INDENT n = len ( arr ) NEW_LINE minRun = calcMinRun ( n ) NEW_LINE for start in range ( 0 , n , minRun ) : NEW_LINE INDENT end = min ( start + minRun - 1 , n - 1 ) NEW_LINE insertionSort ( arr , start , end ) NEW_LINE DEDENT size = minRun NEW_LINE while size < n : NEW_LINE INDENT for left in range ( 0 , n , 2 * size ) : NEW_LINE INDENT mid = min ( n - 1 , left + size - 1 ) NEW_LINE right = min ( ( left + 2 * size - 1 ) , ( n - 1 ) ) NEW_LINE if mid < right : NEW_LINE INDENT merge ( arr , left , mid , right ) NEW_LINE DEDENT DEDENT size = 2 * size NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ - 2 , 7 , 15 , - 14 , 0 , 15 , 0 , 7 , - 7 , - 4 , - 13 , 5 , 8 , - 14 , 12 ] NEW_LINE print ( " Given ▁ Array ▁ is " ) NEW_LINE print ( arr ) NEW_LINE timSort ( arr ) NEW_LINE print ( " After ▁ Sorting ▁ Array ▁ is " ) NEW_LINE print ( arr ) NEW_LINE DEDENT