content: import java.util.Arrays;
  
  public class TimSort {
      private static final int RUN = 32;
  
      public static void timSort(int[] arr) {
          int n = arr.length;
  
          // Sort individual subarrays of size RUN
          for (int i = 0; i < n; i += RUN) {
              insertionSort(arr, i, Math.min(i + RUN - 1, n - 1));
          }
  
          // Merge the sorted subarrays
          for (int size = RUN; size < n; size = 2 * size) {
              for (int left = 0; left < n; left += 2 * size) {
                  int mid = Math.min(left + size - 1, n - 1);
                  int right = Math.min(left + 2 * size - 1, n - 1);
                  if (mid < right) {
                      merge(arr, left, mid, right);
                  }
              }
          }
      }
  
      public static void insertionSort(int[] arr, int left, int right) {
          for (int i = left + 1; i <= right; i++) {
              int key = arr[i];
              int j = i - 1;
              while (j >= left && arr[j] > key) {
                  arr[j + 1] = arr[j];
                  j--;
              }
              arr[j + 1] = key;
          }
      }
  
      public static void merge(int[] arr, int left, int mid, int right) {
          int n1 = mid - left + 1;
          int n2 = right - mid;
          int[] leftArray = new int[n1];
          int[] rightArray = new int[n2];
  
          System.arraycopy(arr, left, leftArray, 0, n1);
          System.arraycopy(arr, mid + 1, rightArray, 0, n2);
  
          int i = 0, j = 0, k = left;
  
          while (i < n1 && j < n2) {
              if (leftArray[i] <= rightArray[j]) {
                  arr[k++] = leftArray[i++];
              } else {
                  arr[k++] = rightArray[j++];
              }
          }
  
          while (i < n1) {
              arr[k++] = leftArray[i++];
          }
  
          while (j < n2) {
              arr[k++] = rightArray[j++];
          }
      }
  
      public static void main(String[] args) {
          int[] arr = {64, 34, 25, 12, 22, 11, 90};
          timSort(arr);
          System.out.println("Sorted array: " + Arrays.toString(arr));
      }
  }
  