Merge-Sort

LeetCode 912: Sort an Array

A clear explanation of sorting an array without built-in sorting using merge sort.

LeetCode 493: Reverse Pairs

A clear explanation of counting pairs where nums[i] is greater than twice nums[j] using merge sort.

LeetCode 327: Count of Range Sum

A clear explanation of Count of Range Sum using prefix sums and merge sort counting.

LeetCode 315: Count of Smaller Numbers After Self

A clear explanation of Count of Smaller Numbers After Self using coordinate compression and a Fenwick Tree.

LeetCode 148: Sort List

Sort a singly linked list in ascending order using merge sort with fast and slow pointers.

GPU Merge Sort

Sort data on a GPU by recursively merging sorted runs using parallel merge primitives.

Parallel Merge Sort

Divide the input, sort subarrays in parallel, then merge them using parallel merge procedures.

Tape Merge Sort

External sorting algorithm that distributes sorted runs across sequential storage tapes and repeatedly merges them.

Cascade Merge Sort

External sorting method that merges sorted runs through staged levels so output from one level feeds the next.

Balanced K Way Merge Sort

External sorting algorithm that repeatedly merges groups of k sorted runs until one final sorted run remains.

Polyphase Merge Sort

External sorting algorithm that distributes sorted runs unevenly across files so repeated merges need fewer empty files and less redistribution.

External Merge Sort

Sort data that does not fit in memory by dividing it into sorted runs and merging them using external storage.

Adaptive Shivers Sort

An adaptive merge-based sorting algorithm that merges natural runs using stack rules designed to minimize merge cost.

Natural Runs Sort

Sort a sequence by detecting already sorted runs and repeatedly merging them.

Adaptive Merge Sort

A merge sort variant that exploits existing order in the input by detecting natural runs and reducing work.

Tournament Merge Sort

Merge-based sorting algorithm that uses a tournament tree to repeatedly select the next smallest element.

Multiway Merge Sort

Merge sort variant that merges more than two sorted sequences at each step.

Cache Oblivious Merge Sort

Merge sort variant that improves locality without tuning parameters for a specific cache size.

Cache Efficient Merge Sort

Merge sort variant designed to improve cache locality by structuring recursion and merging to fit memory hierarchies.

Block Merge Sort

Stable merge sort variant that uses block rearrangement and a small buffer to reduce auxiliary memory.

In Place Merge Sort

Merge sort variant that reduces auxiliary memory by merging sorted ranges inside the original array.

Natural Merge Sort

Adaptive merge sort that detects existing sorted runs and merges them.

Bottom Up Merge Sort

Iterative merge sort that builds sorted runs from size 1 upward without recursion.

Top Down Merge Sort

Recursive merge sort that splits the array from the top and merges sorted halves.

Merge Sort

Divide and conquer sorting algorithm that splits the array, sorts recursively, and merges in linear time.

6.20 Inversion Counting

Count pairs of elements in the wrong relative order to measure how far an array is from sorted, using a modified merge sort in O(n log n) time.

6.4 Merge Sort

Divide the input into halves, recursively sort each half, then merge them — combining local order into global order in O(n log n) time.