Sorting is one of the most common tasks in computer programming. Whether you are arranging numbers, names, or any other data, sorting helps make information more meaningful and easier to process. Many different sorting algorithms exist in computer science, each designed with its own advantages and use cases. Among these, Tim Sort stands out as one of the most powerful and efficient hybrid algorithms ever created.
with hands-on learning.
get the skills and confidence to land your next move.
Tim Sort is a real-world sorting algorithm used in popular programming languages such as Python and Java. It was invented by Tim Peters in 2002 and is named after him. The beauty of Tim Sort lies in the fact that it combines the simplicity of Insertion Sort with the efficiency of Merge Sort, creating an algorithm that performs extremely well on real-world data that is often partially sorted. For beginners learning C programming, implementing Tim Sort is a wonderful way to understand how algorithms can be designed to handle practical data efficiently.
Program 1: Basic Implementation of Tim Sort in C
The first version of Tim Sort we will look at focuses on simplicity. It combines Insertion Sort for smaller chunks (called runs) and Merge Sort for combining these chunks efficiently.
#include <stdio.h>
#include <stdlib.h>
#define RUN 32
// Function to perform insertion sort
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;
}
}
// Function to merge two sorted parts of the array
void merge(int arr[], int l, int m, int r) {
int len1 = m - l + 1, len2 = r - m;
int left[len1], right[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++];
}
// Function to implement Tim Sort
void timSort(int arr[], int n) {
for (int i = 0; i < n; i += RUN)
insertionSort(arr, i, (i + 31 < n - 1) ? i + 31 : 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 = (left + 2 * size - 1 < n - 1) ? left + 2 * size - 1 : n - 1;
if (mid < right)
merge(arr, left, mid, right);
}
}
}
// Function to print the array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {5, 21, 7, 23, 19, 12, 3, 2, 25, 10};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array:\n");
printArray(arr, n);
timSort(arr, n);
printf("Sorted array:\n");
printArray(arr, n);
return 0;
}This program starts by dividing the array into small parts called runs. Each run is sorted using Insertion Sort, which is efficient for small segments. After sorting the runs, it merges them using a Merge Sort style combination. This hybrid approach gives Tim Sort its power — it works well even for partially sorted data, which is common in everyday applications. Beginners can easily follow this program because it clearly separates each step: sorting small parts, then merging them into one sorted array.
Program 2: Tim Sort with User Input
In this version, the program accepts numbers from the user instead of using a fixed array. This makes it interactive and helps learners experiment with different data sets.
#include <stdio.h>
#include <stdlib.h>
#define RUN 32
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;
}
}
void merge(int arr[], int l, int m, int r) {
int len1 = m - l + 1, len2 = r - m;
int left[len1], right[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++];
}
void timSort(int arr[], int n) {
for (int i = 0; i < n; i += RUN)
insertionSort(arr, i, (i + 31 < n - 1) ? i + 31 : 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 = (left + 2 * size - 1 < n - 1) ? left + 2 * size - 1 : n - 1;
if (mid < right)
merge(arr, left, mid, right);
}
}
}
int main() {
int n;
printf("Enter number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d numbers:\n", n);
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
printf("Original array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
timSort(arr, n);
printf("Sorted array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}Here, the user provides the size and elements of the array, allowing for flexibility in testing different values. The logic remains the same as before — small portions are sorted using Insertion Sort, and the merged results produce a completely sorted list. This approach helps learners interact with the algorithm, seeing how it behaves with various inputs.
Frequently Asked Questions (FAQ)
Here are some common questions about Tim Sort and its C implementation.
What makes Tim Sort special compared to other sorting algorithms?
Tim Sort is designed to perform well on real-world data, which often has partially sorted segments. It combines the advantages of Merge Sort and Insertion Sort to achieve excellent performance on practical datasets.
Is Tim Sort faster than Quick Sort or Merge Sort?
In most real-world situations, yes. Tim Sort is faster than traditional sorting algorithms on partially sorted data. Its time complexity in the average and best cases is O(n log n), and it performs well even on large data sets.
Can Tim Sort handle negative numbers or floating-point values?
Yes, Tim Sort can handle any type of numeric data as long as comparisons between elements are valid. It works perfectly for negative numbers, integers, and even floating-point numbers.
Is Tim Sort stable?
Yes, Tim Sort is a stable sorting algorithm, which means it preserves the relative order of elements with equal values. This property makes it ideal for applications like sorting database records.
Conclusion
Tim Sort is a modern, efficient, and practical sorting algorithm that every C programming student should learn. It beautifully combines the logic of Insertion Sort for small portions and Merge Sort for merging, resulting in a hybrid approach that performs well on nearly any type of data.
By practicing the examples above — from basic implementation to user input and handling negative numbers — you’ll gain a strong understanding of how hybrid algorithms work and how combining ideas from multiple methods can lead to powerful results. As you continue learning C programming, experimenting with algorithms like Tim Sort will strengthen both your coding skills and your logical thinking.
