Merge Sort and Radix Sort

Definition

Merge Sort is a comparison-based sorting algorithm that divides an array into smaller subarrays, sorts each subarray, and then merges the sorted subarrays to produce the final sorted list.

Radix Sort is a non-comparison-based sorting algorithm that sorts numbers or strings by processing individual digits, characters, or positions from the least significant to the most significant digit, or vice versa.

Main Content

1. Merge Sort

Divide-and-conquer technique

Merge Sort repeatedly splits the input list into two halves until each sublist contains only one element. A list of one element is already sorted, so this is the base case. After splitting, the algorithm merges the sublists in sorted order.

Stable and predictable performance

Merge Sort maintains the relative order of equal elements, which makes it a stable sort. Its time complexity is consistently O(n log n) in the best, average, and worst cases, making it one of the most reliable sorting algorithms for large datasets.

Example:
Sort the array: 38, 27, 43, 3, 9, 82, 10

Split repeatedly:

38, 27, 43, 3 and 9, 82, 10
38, 27 and 43, 3, 9, 82 and 10
38 27 43 3 9 82 10

Then merge:

38 and 27 → 27, 38
43 and 3 → 3, 43
9 and 82 → 9, 82

Merge again:

27, 38 and 3, 43 → 3, 27, 38, 43
9, 82 and 10 → 9, 10, 82

Final merge:

3, 27, 38, 43 and 9, 10, 82 → 3, 9, 10, 27, 38, 43, 82

2. Radix Sort

Digit-by-digit sorting

Radix Sort processes the elements based on individual digit places. It first groups elements by one digit position and then repeats the process for the next position. The order of processing digits is crucial: for LSD Radix Sort, it begins with the least significant digit; for MSD Radix Sort, it begins with the most significant digit.

Depends on a stable subroutine

Radix Sort usually uses a stable sorting method such as Counting Sort to sort elements at each digit position. Stability is essential because it preserves the order of previous digit-based sorting passes.

Example:
Sort the numbers: 170, 45, 75, 90, 802, 24, 2, 66

Sort by units digit:

170, 90 → digit 0
802, 2 → digit 2
24 → digit 4
45, 75 → digit 5
66 → digit 6

After first pass: 170, 90, 802, 2, 24, 45, 75, 66

Sort by tens digit:

802, 2 → digit 0
24 → digit 2
45 → digit 4
66 → digit 6
170, 75 → digit 7
90 → digit 9

After second pass: 802, 2, 24, 45, 66, 170, 75, 90

Sort by hundreds digit:

2, 24, 45, 66, 75, 90 → digit 0
170 → digit 1
802 → digit 8

Final sorted order: 2, 24, 45, 66, 75, 90, 170, 802

3. Comparison of Merge Sort and Radix Sort

Type of sorting

Merge Sort is a comparison-based algorithm, meaning it sorts by comparing elements directly. Radix Sort is non-comparison-based, meaning it sorts according to digit positions rather than direct pairwise comparisons.

Data suitability and efficiency

Merge Sort works well for many data types, including numbers, strings, and objects, as long as comparisons are defined. Radix Sort is especially efficient for integers, fixed-length strings, or data with a limited digit/character range.

Comparison Table:

Feature	Merge Sort	Radix Sort
Sorting type	Comparison-based	Non-comparison-based
Time complexity	O(n log n)	O(d(n + k))
Space complexity	O(n)	O(n + k)
Stability	Stable	Stable if sub-sort is stable
Best for	General-purpose sorting	Integers / fixed-format keys
Main idea	Divide and merge	Sort by digits/positions

Where:

n = number of elements
d = number of digits/character positions
k = range of digit values

Important conceptual difference:
Merge Sort is limited by the comparison model, so it cannot beat the O(n log n) lower bound for comparison sorts. Radix Sort bypasses this limit by exploiting the structure of the keys.

Working / Process

1. Understand the input and choose the algorithm

If the data is general and comparisons are natural, Merge Sort is a strong choice.
If the data consists of integers or fixed-length keys, Radix Sort may be faster.

2. Apply the sorting process

For Merge Sort, divide the array into halves until single elements remain, then merge them in sorted order.
For Radix Sort, sort the elements digit by digit using a stable intermediate sort like Counting Sort.

3. Combine results into the final sorted output

Merge Sort combines sorted halves repeatedly until the whole array is sorted.
Radix Sort completes all digit passes and returns the fully ordered list.

Process illustration for Merge Sort:

Input: [38, 27, 43, 3, 9, 82, 10]

Split: [38, 27, 43, 3] and [9, 82, 10]

Split again: [38, 27] [43, 3] [9, 82] [10]

Merge sorted parts: [27, 38] [3, 43] [9, 82] [10]

Final merge: [3, 9, 10, 27, 38, 43, 82]

Process illustration for Radix Sort (LSD):

Input: [170, 45, 75, 90, 802, 24, 2, 66]

Pass 1: units digit
Pass 2: tens digit
Pass 3: hundreds digit

Final output: [2, 24, 45, 66, 75, 90, 170, 802]

Advantages / Applications

Merge Sort provides guaranteed performance

It always runs in O(n log n) time, making it dependable even in the worst case.
It is useful when consistent performance matters more than small constant-factor overhead.

Radix Sort can be extremely fast for suitable data

It can sort large sets of integers or strings efficiently when the number of digits or character positions is limited.
It often outperforms comparison-based methods for data with fixed-size keys.

Both algorithms are widely used in practical and academic settings

Merge Sort is used in external sorting, linked-list sorting, and stable sorting tasks.
Radix Sort is used in database indexing, sorting large numerical datasets, and applications involving postal codes, IDs, or fixed-format records.

Applications of Merge Sort:

Sorting linked lists because merging is efficient on linked structures
External sorting for data that does not fit in main memory
Stable sorting in applications where equal items must preserve input order

Applications of Radix Sort:

Sorting integers, especially non-negative integers
Sorting fixed-length strings such as names, codes, or identifiers
Sorting records in systems where digit-wise or character-wise grouping is useful

Summary

Merge Sort sorts by dividing the list and merging sorted halves.
Radix Sort sorts by processing digits or character positions step by step.
Merge Sort is a stable comparison-based algorithm, while Radix Sort is a non-comparison-based algorithm for structured keys.
Important terms to remember: divide and conquer, stable sort, comparison-based, non-comparison-based, counting sort, digit-wise sorting