Sorting is a fundamental skill in programming, and understanding different algorithms can make your code more efficient and effective. Tim Sort is a hybrid sorting algorithm that combines the best parts of Merge Sort and Insertion Sort. Its unique approach makes it particularly efficient for real-world data that is often partially sorted, which is common in many applications.
with hands-on learning.
get the skills and confidence to land your next move.
Tim Sort is used in programming languages such as Python and Java for built-in sorting functions. Learning Tim Sort in Java allows beginners to explore hybrid algorithms, understand how small optimizations can improve performance, and apply these concepts to larger, more complex programs. It’s also a great way to learn how sorting algorithms can handle both small and large datasets efficiently.
Program 1: Basic Tim Sort Implementation Using Runs and Merge
This program demonstrates the core idea of Tim Sort using a combination of Insertion Sort for small segments and Merge Sort for merging these segments. It gives a solid foundation for understanding how Tim Sort works.
public class TimSortExample1 {
static int RUN = 32;
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, j = 0, k = l;
while (i < len1 && j < len2) {
if (left[i] <= right[j]) arr[k++] = left[i++];
else arr[k++] = right[j++];
}
while (i < len1) arr[k++] = left[i++];
while (j < len2) arr[k++] = right[j++];
}
public static void timSort(int[] arr, int n) {
for (int i = 0; i < n; i += RUN) {
insertionSort(arr, i, Math.min((i + RUN - 1), (n - 1)));
}
for (int size = RUN; 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 main(String[] args) {
int[] arr = {23, 12, 1, 8, 34, 54, 2, 3};
System.out.println("Original Array:");
for (int num : arr) System.out.print(num + " ");
System.out.println();
timSort(arr, arr.length);
System.out.println("Sorted Array:");
for (int num : arr) System.out.print(num + " ");
}
}This basic Tim Sort first divides the array into small segments and sorts them using Insertion Sort. Then, it merges these segments using Merge Sort. Beginners can see how combining simple algorithms can create an efficient hybrid.
Program 2: Tim Sort with Dynamic Run Sizes
This program shows how Tim Sort can adapt run sizes dynamically. Instead of a fixed run size, we calculate an optimal run size for each dataset. This can improve performance, especially on partially sorted arrays.
public class DynamicTimSort {
public static int minRunLength(int n) {
int r = 0;
while (n >= 64) {
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;
int len2 = r - m;
int[] left = new int[len1];
int[] right = new int[len2];
for (int i = 0; i < len1; i++) left[i] = arr[l + i];
for (int i = 0; i < len2; i++) right[i] = arr[m + 1 + i];
int i = 0, j = 0, k = l;
while (i < len1 && j < len2) {
if (left[i] <= right[j]) arr[k++] = left[i++];
else arr[k++] = right[j++];
}
while (i < len1) arr[k++] = left[i++];
while (j < len2) arr[k++] = right[j++];
}
public static void timSort(int[] arr) {
int n = arr.length;
int minRun = minRunLength(n);
for (int i = 0; i < n; i += minRun) {
insertionSort(arr, i, Math.min(i + minRun - 1, n - 1));
}
for (int size = minRun; size < n; size *= 2) {
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 main(String[] args) {
int[] arr = {10, 3, 15, 7, 8, 23, 74, 18};
System.out.println("Original Array:");
for (int num : arr) System.out.print(num + " ");
System.out.println();
timSort(arr);
System.out.println("Sorted Array:");
for (int num : arr) System.out.print(num + " ");
}
}This program calculates the minimum run length dynamically based on the array size, which can optimize performance on partially sorted data. Beginners can appreciate how Tim Sort is designed to adapt to real-world data, combining the simplicity of Insertion Sort for small runs with the efficiency of Merge Sort for larger merges.
Program 3: Tim Sort for Nearly Sorted Arrays
Tim Sort is especially fast for arrays that are already partially sorted. This program demonstrates its efficiency with a nearly sorted dataset.
public class TimSortExample3 {
static int RUN = 32;
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, j = 0, k = l;
while (i < len1 && j < len2) {
if (left[i] <= right[j]) arr[k++] = left[i++];
else arr[k++] = right[j++];
}
while (i < len1) arr[k++] = left[i++];
while (j < len2) arr[k++] = right[j++];
}
public static void timSort(int[] arr, int n) {
for (int i = 0; i < n; i += RUN) {
insertionSort(arr, i, Math.min((i + RUN - 1), (n - 1)));
}
for (int size = RUN; size < n; size *= 2) {
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 main(String[] args) {
int[] arr = {1, 2, 3, 5, 4, 6, 7, 8};
System.out.println("Original Array:");
for (int num : arr) System.out.print(num + " ");
System.out.println();
timSort(arr, arr.length);
System.out.println("Sorted Array:");
for (int num : arr) System.out.print(num + " ");
}
}Beginners can see how Tim Sort efficiently handles nearly sorted arrays, often completing in fewer steps than standard sorting algorithms.
Program 4: Tim Sort with Recursion for Merge
This example highlights a recursive approach for merging segments, which can simplify logic and improve readability.
public class TimSortExample4 {
static int RUN = 32;
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, j = 0, k = l;
while (i < len1 && j < len2) {
if (left[i] <= right[j]) arr[k++] = left[i++];
else arr[k++] = right[j++];
}
while (i < len1) arr[k++] = left[i++];
while (j < len2) arr[k++] = right[j++];
}
public static void recursiveMergeSort(int[] arr, int l, int r) {
if (l >= r) return;
int m = l + (r - l) / 2;
recursiveMergeSort(arr, l, m);
recursiveMergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
public static void main(String[] args) {
int[] arr = {29, 10, 14, 37, 13, 5};
System.out.println("Original Array:");
for (int num : arr) System.out.print(num + " ");
System.out.println();
recursiveMergeSort(arr, 0, arr.length - 1);
System.out.println("Sorted Array:");
for (int num : arr) System.out.print(num + " ");
}
}Recursion allows merging to happen in a structured manner, helping beginners understand the divide-and-conquer approach behind Tim Sort.
Program 5: Tim Sort for Floating-Point Numbers
Tim Sort can also be adapted for decimals. This program sorts an array of floating-point numbers in Java.
public class TimSortExample5 {
static int RUN = 32;
// Insertion Sort for small segments
public static void insertionSort(double[] arr, int left, int right) {
for (int i = left + 1; i <= right; i++) {
double temp = arr[i];
int j = i - 1;
while (j >= left && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
// Merge function for two sorted halves
public static void merge(double[] arr, int l, int m, int r) {
int len1 = m - l + 1, len2 = r - m;
double[] left = new double[len1];
double[] right = new double[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, j = 0, k = l;
while (i < len1 && j < len2) {
if (left[i] <= right[j]) arr[k++] = left[i++];
else arr[k++] = right[j++];
}
while (i < len1) arr[k++] = left[i++];
while (j < len2) arr[k++] = right[j++];
}
// TimSort main function
public static void timSort(double[] arr, int n) {
// Sort small segments with insertion sort
for (int i = 0; i < n; i += RUN) {
insertionSort(arr, i, Math.min((i + RUN - 1), (n - 1)));
}
// Merge sorted runs
for (int size = RUN; size < n; size *= 2) {
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 main(String[] args) {
double[] arr = {23.5, 12.1, 1.0, 8.6, 34.3, 2.2};
System.out.println("Original Array:");
for (double num : arr) System.out.print(num + " ");
System.out.println();
timSort(arr, arr.length);
System.out.println("Sorted Array:");
for (double num : arr) System.out.print(num + " ");
}
}This example demonstrates that Tim Sort is flexible and can handle different numeric types with ease. Beginners see the algorithm’s adaptability to real-world data.
Program 6: Using Java’s Arrays.sort() (Tim Sort Under the Hood)
This program demonstrates how Java’s Arrays.sort() method automatically uses Tim Sort for object arrays. It is the easiest way to sort arrays efficiently without writing a custom algorithm.
import java.util.Arrays;
public class ArraysSortTimSortExample {
public static void main(String[] args) {
Integer[] arr = {42, 12, 5, 89, 33, 7, 21};
System.out.println("Original Array:");
System.out.println(Arrays.toString(arr));
// Arrays.sort() uses Tim Sort for object arrays
Arrays.sort(arr);
System.out.println("Sorted Array:");
System.out.println(Arrays.toString(arr));
}
}In this example, Arrays.sort(arr) sorts the array in ascending order. Internally, Java applies Tim Sort to object arrays, combining Insertion Sort for small subarrays with Merge Sort for larger merges. Beginners can quickly leverage Tim Sort’s efficiency without implementing it manually, making it perfect for practical applications and real-world coding projects.
Program 7: Sorting a String Array Alphabetically
Arrays.sort() can also sort arrays of strings. It sorts them lexicographically (alphabetical order).
import java.util.Arrays;
public class SortStrings {
public static void main(String[] args) {
String[] fruits = {"Banana", "Apple", "Mango", "Cherry"};
System.out.println("Original Array:");
System.out.println(Arrays.toString(fruits));
Arrays.sort(fruits); // Sorts alphabetically
System.out.println("Sorted Array:");
System.out.println(Arrays.toString(fruits));
}
}In this case, the array of strings is sorted alphabetically. This shows beginners that Arrays.sort() works not only with numbers but also with text, making it versatile for many programming scenarios.
Program 8: Sorting an Array in Descending Order Using a Comparator
By default, Arrays.sort() sorts in ascending order. To sort in descending order or with a custom order, you can use Arrays.sort() with a Comparator.
import java.util.Arrays;
import java.util.Collections;
public class SortDescending {
public static void main(String[] args) {
Integer[] numbers = {42, 12, 5, 89, 33};
System.out.println("Original Array:");
System.out.println(Arrays.toString(numbers));
Arrays.sort(numbers, Collections.reverseOrder()); // Descending order
System.out.println("Sorted Array (Descending):");
System.out.println(Arrays.toString(numbers));
}
}Notice that we use Integer[] instead of int[] because Collections.reverseOrder() works with objects, not primitive types. This example helps beginners understand how to customize sorting beyond the default behavior.
Using Arrays.sort() is one of the simplest and most efficient ways to sort arrays in Java. You can sort numbers, strings, or objects, and even define custom orderings using comparators. It’s a great tool for beginners to master before moving on to writing custom sorting algorithms like Tim Sort or Quick Sort.
Frequently Asked Questions (FAQ)
Tim Sort is widely used, and beginners often have questions about its implementation and performance.
Q1: What is the time complexity of Tim Sort?
The worst-case complexity is O(n log n), while the best case is O(n) for nearly sorted arrays.
Q2: Why use Tim Sort over Quick Sort or Merge Sort?
Tim Sort is optimized for real-world scenarios where data is often partially sorted, making it faster in practice.
Q3: Is Tim Sort stable?
Yes, Tim Sort preserves the relative order of equal elements.
Q4: Can Tim Sort sort decimal numbers?
Absolutely. Tim Sort can handle integers, decimals, and even custom comparable objects.
Q5: Where is Tim Sort used in programming?
Tim Sort is used in Python’s sorted() function, Java’s Arrays.sort() for objects, and other standard libraries that require efficient, stable sorting.
Conclusion
Tim Sort is a hybrid algorithm that intelligently combines Insertion Sort and Merge Sort to achieve efficiency and stability. In this article, we explored multiple Java implementations, including basic sorting, custom RUN sizes, nearly sorted arrays, recursive merging, and handling floating-point numbers.
Beginners practicing these examples gain a deeper understanding of hybrid algorithms, recursion, and real-world optimization. Experimenting with Tim Sort helps build a strong foundation for tackling more advanced sorting challenges and writing efficient code in real applications.
