tag

#radix-sort

25 pages tagged

Practice › LeetCode › LeetCode 23xx ›

LeetCode 2343 - Query Kth Smallest Trimmed Number

LeetCode Problem 2343 Difficulty: 🟡 Medium Topics: Array, String, Divide and Conquer, Sorting, Heap (Priority Queue), Radix Sort, Quickselect Solution Problem Understanding This problem provides a list of numbers represented as strings, all of equal length. The task is to answer multiple queries, where each query asks for the index of the k-th smallest number after trimming every number in the list to its last trimi digits. Importantly, if two...
leetcode Medium array string divide-and-conquer sorting heap-(priority-queue) radix-sort quickselect May 29, 2026
Practice › LeetCode › LeetCode 09xx ›

LeetCode 912 - Sort an Array

LeetCode Problem 912 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Sorting, Heap (Priority Queue), Merge Sort, Bucket Sort, Radix Sort, Counting Sort Solution Problem Understanding The problem asks us to sort an integer array in ascending order without using any built in sorting functions. The result must contain the same elements as the input, but arranged from smallest to largest. The input is an array nums containing integers. These...
leetcode Medium array divide-and-conquer sorting heap-(priority-queue) merge-sort bucket-sort radix-sort counting-sort May 28, 2026
Practice › LeetCode › LeetCode 01xx ›

LeetCode 164 - Maximum Gap

LeetCode Problem 164 Difficulty: 🟡 Medium Topics: Array, Sorting, Bucket Sort, Radix Sort Solution Problem Understanding The problem asks us to compute the largest difference between two consecutive elements after sorting the array . At first glance, this may seem straightforward: sort the array, then scan through adjacent pairs to find the maximum difference. However, there is an important constraint: the algorithm must run in linear time, O(n), and use...
leetcode Medium array sorting bucket-sort radix-sort May 27, 2026
Practice › LeetCode › LeetCode (archived) › LeetCode 01xx ›

LeetCode 164: Maximum Gap

Problem Restatement We are given an integer array nums . We need to imagine the array sorted in ascending order, then return the maximum difference between two successive elements. If the array has fewer than two elements, return 0 . The problem also requires an algorithm that runs in linear time and uses linear extra space. LeetCode states the constraints as 1 <= nums.length <= 10^5 and 0 <= nums[i]...
leetcode array bucket-sort radix-sort sorting May 10, 2026
Wiki › Algorithms › 01. Searching and Sorting ›

8. Integer and Distribution Sorting

8. Integer and distribution sorting, 40 index slug name 216 counting-sort Counting Sort 217 stable-counting-sort Stable Counting Sort 218 key-indexed-counting Key Indexed Counting 219 radix-sort Radix Sort 220 lsd-radix-sort LSD Radix Sort 221 msd-radix-sort MSD Radix Sort 222 american-flag-sort American Flag Sort 223 in-place-radix-sort In Place Radix Sort 224 binary-radix-sort Binary Radix Sort 225 burstsort Burstsort 226 bucket-sort Bucket Sort 227 uniform-bucket-sort Uniform Bucket Sort 228 histogram-sort Histogram Sort 229...
algorithms sorting radix-sort distribution-sort May 6, 2026
Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.8 Radix Sort

6.8 Radix Sort Radix sort sorts keys one digit at a time. It avoids direct comparisons between full keys by repeatedly applying a stable sort to smaller key components. For integers, those components are usually digits in base 10 , base 256 , or another fixed radix. Problem You have an array of nonnegative integers. You want to sort them in linear time relative to the number of elements and...
algorithms sorting radix-sort linear-time May 4, 2026
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

In Place Radix Sort

In Place Radix Sort In place radix sort sorts keys by digits while avoiding a full auxiliary output array. It keeps only small bucket metadata, such as counts, offsets, and next write positions. The common form is MSD based. At each digit position, the algorithm partitions the current subarray into digit buckets, then recursively sorts each bucket by the next digit. Problem Given an array $A$ of keys whose digits...
algorithms sorting radix-sort in-place-sorting
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Binary Radix Sort

Binary Radix Sort Binary radix sort sorts integers by examining their binary representation bit by bit. Instead of using counting arrays, it partitions elements into two groups based on whether a bit is 0 or 1. This yields a simple and memory efficient radix sort specialized for base 2. Problem Given an array $A$ of integers, sort them in increasing order using their binary representation. Each number can be written...
algorithms sorting radix-sort binary-radix-sort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Word Radix Sort

Word Radix Sort Word radix sort is a radix sorting method specialized for fixed width machine words such as 32 bit or 64 bit integers. It processes keys a byte or group of bits at a time using fast bit operations. This approach matches hardware representation and is widely used in high performance systems. Problem Given an array $A$ of $n$ fixed width integers, sort the array efficiently. Each key...
algorithms sorting radix-sort word-radix-sort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Radix Sort

Radix Sort Radix sort sorts keys by decomposing them into smaller parts such as digits, bytes, or characters. Instead of comparing whole keys directly, it groups keys by one position at a time. It is most useful when keys have fixed width or bounded length, such as integers, fixed length strings, byte arrays, or identifiers. Problem Given an array $A$ of $n$ keys, sort the keys by their full value...
algorithms sorting radix-sort integer-sorting
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Least Significant Byte Sort

Least Significant Byte Sort Least Significant Byte sort is the byte oriented version of LSD radix sort. It processes fixed width keys one byte at a time, starting from the least significant byte and moving toward the most significant byte. It relies on a stable inner sorting step, usually counting sort with 256 buckets. Problem Given an array $A$ of fixed width integer keys, sort the array in increasing order....
algorithms sorting radix-sort lsb-sort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Radix Exchange Sort

Radix Exchange Sort Radix exchange sort is an in place radix sorting algorithm for binary keys, usually integers. It processes bits from most significant to least significant and partitions the array into two regions at each bit. At each step, all keys with bit 0 move before all keys with bit 1. The algorithm then recursively sorts both regions using the next bit. Problem Given an array $A$ of nonnegative...
algorithms sorting radix-sort radix-exchange-sort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Most Significant Byte Sort

Most Significant Byte Sort Most Significant Byte sort is an MSD radix sort that processes fixed-width keys one byte at a time, starting from the most significant byte. It partitions the array into byte buckets and recursively sorts each bucket using the next byte. It is effective for large datasets and for keys where higher-order bytes quickly distinguish values. Problem Given an array $A$ of $n$ fixed-width keys (such as...
algorithms sorting radix-sort msb-sort
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

External Radix Sort

External Radix Sort External radix sort extends radix sort to datasets larger than memory. It processes keys digit by digit and uses external storage to hold intermediate buckets. Unlike comparison-based external sorts, it exploits the structure of keys to achieve linear-time sorting. This method is effective when keys have fixed length or can be decomposed into digits. Problem Given a large dataset with keys that can be decomposed into digits...
algorithms sorting external-memory radix-sort
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

Parallel Radix Sort

Parallel Radix Sort Parallel radix sort sorts fixed width keys by processing one digit group at a time. A digit group may be a byte, a few bits, or another small radix unit. Each pass groups elements by the current digit while preserving the order needed by the radix variant. For integer keys, parallel radix sort is often faster than comparison sorting because it uses key digits directly. Its main...
algorithms sorting parallel radix-sort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Bytewise Radix Sort

Bytewise Radix Sort Bytewise radix sort sorts fixed-width keys by processing one 8-bit byte at a time. Since each byte has 256 possible values, every pass uses a counting array of size 256. It is a practical form of radix sort for machine integers, binary records, and fixed-size keys because byte extraction is cheap and bucket arrays fit easily in cache. Problem Given an array $A$ of $n$ fixed-width unsigned...
algorithms sorting radix-sort bytewise-radix-sort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Signed Integer Radix Sort

Signed Integer Radix Sort Signed integer radix sort extends radix sorting to handle both negative and positive integers correctly. Since radix sort operates on digit or bit patterns, special handling is required to maintain numeric ordering. Problem Given an array $A$ of signed integers, sort the array in increasing order. Integers are represented in two's complement form, where direct unsigned interpretation does not preserve ordering. Idea Transform each integer into...
algorithms sorting radix-sort integer-sorting
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

GPU Radix Sort

GPU Radix Sort GPU radix sort sorts fixed width integer keys by processing a small number of bits at a time. Each pass groups keys by the current digit. On GPUs, the main work is building histograms, computing prefix sums, and scattering keys into their next positions. For integer keys, GPU radix sort is often one of the fastest general sorting methods because it avoids comparisons and exposes large amounts...
algorithms sorting gpu radix-sort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

American Flag Sort

American Flag Sort American flag sort is an in place variant of radix sort. It distributes elements into buckets based on a digit, then permutes them into correct positions using cycle leader permutation. Unlike standard radix sort, it avoids auxiliary arrays. This algorithm is commonly used for large datasets where memory allocation must be minimized. Problem Given an array $A$ of keys with digits in range $[0, b)$, reorder the...
algorithms sorting radix-sort american-flag-sort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

American Flag String Sort

American Flag String Sort American flag string sort is an in-place MSD radix sort for strings. It partitions strings by the character at the current position, then recursively sorts each bucket by the next character. It uses the same bucket permutation idea as American flag sort, but the digit source is a string character rather than an integer digit. Problem Given an array $A$ of strings, sort the strings in...
algorithms sorting string-sorting radix-sort american-flag-sort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Floating Point Radix Sort

Floating Point Radix Sort Floating point radix sort sorts floating point numbers by transforming their binary representation into an order-preserving integer form, then applying standard radix sort. The main challenge is that IEEE floating point bit ordering does not match numeric ordering for negative values. Problem Given an array $A$ of floating point numbers (typically IEEE 754), sort the array in increasing order. Idea Each floating point number is represented...
algorithms sorting radix-sort floating-point
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Suffix Array Radix Sort

Suffix Array Radix Sort Suffix array radix sort is the radix-optimized version of the suffix array doubling method. It still sorts suffixes by rank pairs, but uses counting sort or radix sort instead of comparison sorting. This reduces each doubling round from comparison sorting over pairs to linear sorting over integer ranks. Problem Given a string $S$ of length $n$, construct the suffix array: $$ SA = \text{sorted indices of...
algorithms sorting string-processing suffix-array radix-sort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

LSD Radix Sort

LSD Radix Sort LSD radix sort sorts keys by scanning digit positions from right to left, starting with the least significant digit. Each pass uses a stable sorting method on one digit position. The usual inner method is stable counting sort. Stability is essential because later passes must preserve the order already established by earlier, less significant digits. Problem Given $n$ keys of fixed width $m$, where each digit is...
algorithms sorting radix-sort lsd-radix-sort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

MSD Radix Sort

MSD Radix Sort MSD radix sort processes digits from most significant to least significant. It partitions the array by the leading digit, then recursively sorts each partition. This approach follows lexicographic order naturally and works well for strings and variable length keys. Problem Given an array $A$ of $n$ keys, each represented as a sequence of digits or characters, sort them lexicographically. A key can be written as: $$ x...
algorithms sorting radix-sort msd-radix-sort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Ska Sort

Ska Sort Ska sort is a high performance radix sorting algorithm designed for modern CPUs. It focuses on minimizing cache misses, branch mispredictions, and memory movement by using block based partitioning and branchless classification. It is particularly effective for sorting large arrays of integers, pointers, or fixed width keys. Problem Given an array $A$ of fixed width keys, sort it efficiently using a radix based method optimized for hardware performance....
algorithms sorting radix-sort ska-sort