TimSort | Java program to perform 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 ] ; Utility function to print the Array ; Driver code ; Function Call
class GFG { static int MIN_MERGE = 32 ; public static int minRunLength ( int n ) { assert n >= 0 ; int r = 0 ; while ( n >= MIN_MERGE ) { r |= ( n & 1 ) ; n >>= 1 ; } return n + r ; } public static void insertionSort ( int [ ] arr , int left , int right ) { for ( int i = left + 1 ; i <= right ; i ++ ) { int temp = arr [ i ] ; int j = i - 1 ; while ( j >= left && arr [ j ] > temp ) { arr [ j + 1 ] = arr [ j ] ; j -- ; } arr [ j + 1 ] = temp ; } } public static void merge ( int [ ] arr , int l , int m , int r ) { int len1 = m - l + 1 , len2 = r - m ; int [ ] left = new int [ len1 ] ; int [ ] right = new int [ len2 ] ; for ( int x = 0 ; x < len1 ; x ++ ) { left [ x ] = arr [ l + x ] ; } for ( int x = 0 ; x < len2 ; x ++ ) { right [ x ] = arr [ m + 1 + x ] ; } int i = 0 ; int j = 0 ; int k = l ; while ( i < len1 && j < len2 ) { if ( left [ i ] <= right [ j ] ) { arr [ k ] = left [ i ] ; i ++ ; } else { arr [ k ] = right [ j ] ; j ++ ; } k ++ ; } while ( i < len1 ) { arr [ k ] = left [ i ] ; k ++ ; i ++ ; } while ( j < len2 ) { arr [ k ] = right [ j ] ; k ++ ; j ++ ; } } public static void timSort ( int [ ] arr , int n ) { int minRun = minRunLength ( MIN_MERGE ) ; for ( int i = 0 ; i < n ; i += minRun ) { insertionSort ( arr , i , Math . min ( ( i + MIN_MERGE - 1 ) , ( n - 1 ) ) ) ; } for ( int size = minRun ; size < n ; size = 2 * size ) { for ( int left = 0 ; left < n ; left += 2 * size ) { int mid = left + size - 1 ; int right = Math . min ( ( left + 2 * size - 1 ) , ( n - 1 ) ) ; if ( mid < right ) merge ( arr , left , mid , right ) ; } } } public static void printArray ( int [ ] arr , int n ) { for ( int i = 0 ; i < n ; i ++ ) { System . out . print ( arr [ i ] + " ▁ " ) ; } System . out . print ( "NEW_LINE"); } public static void main ( String [ ] args ) { int [ ] arr = { - 2 , 7 , 15 , - 14 , 0 , 15 , 0 , 7 , - 7 , - 4 , - 13 , 5 , 8 , - 14 , 12 } ; int n = arr . length ; System . out . println ( " Given ▁ Array ▁ is " ) ; printArray ( arr , n ) ; timSort ( arr , n ) ; System . out . println ( " After ▁ Sorting ▁ Array ▁ is " ) ; printArray ( arr , n ) ; } }