Sorting Algorithms

Timsort

Timsort is sorting algorithm used in real-world programming languages like Python and Java. It works by looking for small already sorted parts (called runs) in the data and then combining them smartly.

If it finds a part that's already sorted, it keeps it that way and just builds around it. It mixes the best ideas from Insertion Sort (good for small data) and Merge Sort (good for big data).

Counting Sort

Counting Sort is a non-comparison-based sorting algorithm that works by counting the number of occurrences of each distinct element in the input, storing those counts in an auxiliary array, and then calculating positions to place each element in the sorted output. It runs in O(n + k) time, where k is the range of input values, making it extremely fast when the range is small compared to n. In the Android OS, it can be useful in scenarios like sorting process priorities, sensor event timestamps within bounded ranges, or color values in image processing, where the possible values are limited and known in advance. Unlike comparison-based algorithms such as QuickSort or MergeSort (which have O(n log n) lower bounds), Counting Sort leverages direct indexing rather than element comparisons, allowing linear-time sorting for bounded integer ranges. It is preferred when data size is large but value range is small and integers-based, and stability is required for preserving order of equal elements.

It's like counting how many people got each score in a test and then arranging them in order.

Merge Sort

Merge Sort breaks your list into two halves again and again until each part has just one item. Then it starts merging them back in order.

Think of it like sorting small piles of cards, then merging those piles together into one big sorted pile.