Sorting is a fundamental concept in programming, and knowing how to efficiently sort data is crucial for many real-world applications. Tim Sort is a hybrid sorting algorithm that combines the efficiency of Merge Sort and the simplicity of Insertion Sort. It is designed to perform well on real-world data by taking advantage of already sorted sequences, called “runs,” within an array. This makes it extremely efficient for nearly sorted or partially sorted datasets.
with hands-on learning.
get the skills and confidence to land your next move.
For beginners, learning Tim Sort in Dart is a great way to understand how algorithms can be optimized to handle practical scenarios rather than just theoretical cases. Tim Sort is widely used in programming languages like Python and Java for built-in sorting functions. Implementing it yourself helps you grasp key algorithmic concepts such as recursion, merging, and optimization strategies for nearly sorted data.
Program 1: Basic Tim Sort Implementation
This program demonstrates the core idea of Tim Sort by combining Insertion Sort for small segments and Merge Sort for combining them. It provides a basic understanding of how the algorithm works.
void insertionSort(List<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;
}
}
void merge(List<int> arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
List<int> left = List<int>.filled(n1, 0);
List<int> right = List<int>.filled(n2, 0);
for (int i = 0; i < n1; i++) left[i] = arr[l + i];
for (int j = 0; j < n2; j++) right[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
arr[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
}
while (i < n1) arr[k++] = left[i++];
while (j < n2) arr[k++] = right[j++];
}
void timSort(List<int> arr, int n) {
int RUN = 32;
for (int i = 0; i < n; i += RUN) {
insertionSort(arr, i, (i + RUN - 1 < n - 1) ? 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 = (left + 2 * size - 1 < n - 1) ? left + 2 * size - 1 : n - 1;
if (mid < right) merge(arr, left, mid, right);
}
}
}
void main() {
List<int> numbers = [23, 12, 1, 8, 34, 54, 2, 3];
print("Original Array: $numbers");
timSort(numbers, numbers.length);
print("Sorted Array: $numbers");
}In this program, small segments of the array are first sorted using Insertion Sort, which is efficient for small data sizes. Then, these segments are merged using Merge Sort to produce a fully sorted array. This combination makes Tim Sort efficient for nearly sorted data and beginners can observe the interplay between different sorting techniques.
Program 2: Tim Sort with Custom RUN Size
This program shows how changing the size of the initial segments (RUN) affects performance. Beginners can experiment with different values to see the impact.
void insertionSort(List<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;
}
}
void merge(List<int> arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
List<int> left = List<int>.filled(n1, 0);
List<int> right = List<int>.filled(n2, 0);
for (int i = 0; i < n1; i++) left[i] = arr[l + i];
for (int j = 0; j < n2; j++) right[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
arr[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
}
while (i < n1) arr[k++] = left[i++];
while (j < n2) arr[k++] = right[j++];
}
void timSortCustomRun(List<int> arr, int n, int RUN) {
for (int i = 0; i < n; i += RUN) {
insertionSort(arr, i, (i + RUN - 1 < n - 1) ? 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 = (left + 2 * size - 1 < n - 1) ? left + 2 * size - 1 : n - 1;
if (mid < right) merge(arr, left, mid, right);
}
}
}
void main() {
List<int> numbers = [45, 23, 53, 12, 3, 8, 1];
print("Original Array: $numbers");
timSortCustomRun(numbers, numbers.length, 16);
print("Sorted Array: $numbers");
}This demonstrates that the choice of RUN size affects the initial sorting stage. Beginners learn that algorithm parameters can optimize performance for specific datasets.
Program 3: Tim Sort for Floating-Point Numbers
Tim Sort is not limited to integers. This program sorts an array of floating-point numbers in Dart.
void insertionSort(List<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;
}
}
void merge(List<int> arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
List<int> left = List<int>.filled(n1, 0);
List<int> right = List<int>.filled(n2, 0);
for (int i = 0; i < n1; i++) left[i] = arr[l + i];
for (int j = 0; j < n2; j++) right[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
arr[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
}
while (i < n1) arr[k++] = left[i++];
while (j < n2) arr[k++] = right[j++];
}
void timSort(List<int> arr, int n) {
int RUN = 32;
for (int i = 0; i < n; i += RUN) {
insertionSort(arr, i, (i + RUN - 1 < n - 1) ? 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 = (left + 2 * size - 1 < n - 1) ? left + 2 * size - 1 : n - 1;
if (mid < right) merge(arr, left, mid, right);
}
}
}
void main() {
List<double> numbers = [23.5, 12.1, 1.0, 8.6, 34.3, 2.2];
print("Original Array: $numbers");
List<int> intNumbers = numbers.map((e) => (e * 10).toInt()).toList();
timSort(intNumbers, intNumbers.length);
List<double> sortedNumbers = intNumbers.map((e) => e / 10).toList();
print("Sorted Array: $sortedNumbers");
}This example shows how Tim Sort can handle floating-point numbers with simple transformations. Beginners see the flexibility of the algorithm for different numeric types.
Program 4: Recursive Tim Sort Merge
This program demonstrates a recursive approach to the merging phase, giving beginners insight into how recursion can simplify logic.
void merge(List<int> arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
List<int> left = List<int>.filled(n1, 0);
List<int> right = List<int>.filled(n2, 0);
for (int i = 0; i < n1; i++) left[i] = arr[l + i];
for (int j = 0; j < n2; j++) right[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
arr[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
}
while (i < n1) arr[k++] = left[i++];
while (j < n2) arr[k++] = right[j++];
}
void recursiveMergeSort(List<int> arr, int l, int r) {
if (l >= r) return; // Base case: 1 element
int mid = (l + r) ~/ 2;
// Recursively sort left and right halves
recursiveMergeSort(arr, l, mid);
recursiveMergeSort(arr, mid + 1, r);
// Merge the sorted halves
merge(arr, l, mid, r);
}
void main() {
List<int> numbers = [29, 10, 14, 37, 13, 5];
print("Original Array: $numbers");
recursiveMergeSort(numbers, 0, numbers.length - 1);
print("Sorted Array: $numbers");
}Recursion allows merging smaller runs systematically. Beginners understand how breaking a problem into smaller stages simplifies the overall sorting process.
Program 5: Tim Sort for Nearly Sorted Array
Tim Sort shines when the array is nearly sorted. This program demonstrates sorting an almost sorted array to highlight efficiency.
void insertionSort(List<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;
}
}
void merge(List<int> arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
List<int> left = List<int>.filled(n1, 0);
List<int> right = List<int>.filled(n2, 0);
for (int i = 0; i < n1; i++) left[i] = arr[l + i];
for (int j = 0; j < n2; j++) right[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
arr[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
}
while (i < n1) arr[k++] = left[i++];
while (j < n2) arr[k++] = right[j++];
}
void timSort(List<int> arr, int n) {
int RUN = 32;
for (int i = 0; i < n; i += RUN) {
insertionSort(arr, i, (i + RUN - 1 < n - 1) ? 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 = (left + 2 * size - 1 < n - 1) ? left + 2 * size - 1 : n - 1;
if (mid < right) merge(arr, left, mid, right);
}
}
}
void main() {
List<int> numbers = [1, 2, 3, 5, 4, 6, 7, 8];
print("Original Array: $numbers");
timSort(numbers, numbers.length);
print("Sorted Array: $numbers");
}Since only a small portion of the array is unsorted, Tim Sort completes the task quickly. Beginners learn why Tim Sort is preferred in real-world scenarios where data is often partially sorted.
Frequently Asked Questions (FAQ)
Tim Sort is a powerful algorithm, and beginners often have questions:
Q1: What is the time complexity of Tim Sort?
The worst-case complexity is O(n log n), and the best case is O(n) when the array is nearly sorted.
Q2: Why use Tim Sort instead of Merge Sort or Quick Sort?
Tim Sort is optimized for real-world data, especially partially sorted arrays, making it faster in practical scenarios.
Q3: Is Tim Sort stable?
Yes, Tim Sort is a stable sorting algorithm, meaning equal elements maintain their relative order.
Q4: Can Tim Sort handle decimals?
Yes, it can sort floating-point numbers and other comparable types.
Q5: Where is Tim Sort used?
It is used in Python’s sorted() function, Java’s Arrays.sort() for objects, and many other programming libraries.
Conclusion
Tim Sort is a versatile and efficient algorithm that combines the strengths of Insertion Sort and Merge Sort. In this article, we explored multiple Dart implementations, including basic sorting, custom RUN sizes, decimal handling, recursion, and nearly sorted arrays.
For beginners, practicing Tim Sort helps understand hybrid algorithms, recursion, and real-world optimizations. Experimenting with parameters and different data types strengthens algorithmic thinking and prepares you for more advanced sorting challenges confidently.
