merge-sort | brain

Practice › LeetCode › LeetCode 37xx ›

LeetCode 3739 - Count Subarrays With Majority Element II

LeetCode Problem 3739 Difficulty: 🔴 Hard Topics: Array, Hash Table, Divide and Conquer, Segment Tree, Merge Sort, Prefix Sum Solution Here’s a complete, detailed technical solution guide for LeetCode 3739 - Count Subarrays With Majority Element II following your requested format. Problem Understanding The problem asks us to count the number of contiguous subarrays in which a given target element is the majority element . A majority element is one...

Practice › LeetCode › LeetCode 37xx ›

LeetCode 3737 - Count Subarrays With Majority Element I

LeetCode Problem 3737 Difficulty: 🟡 Medium Topics: Array, Hash Table, Divide and Conquer, Segment Tree, Merge Sort, Counting, Prefix Sum Solution Here is a comprehensive, detailed reference guide for LeetCode 3737 - Count Subarrays With Majority Element I , following your formatting requirements exactly. Problem Understanding The problem provides an integer array nums and a target integer. The goal is to count the number of subarrays in which the target...

Practice › LeetCode › LeetCode 24xx ›

LeetCode 2426 - Number of Pairs Satisfying Inequality

LeetCode Problem 2426 Difficulty: 🔴 Hard Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution LeetCode 2426 - Number of Pairs Satisfying Inequality Problem Understanding We are given two integer arrays, nums1 and nums2 , of the same length n , along with an integer diff . We must count how many index pairs (i, j) satisfy both: i < j nums1[i]...

Practice › LeetCode › LeetCode 21xx ›

LeetCode 2179 - Count Good Triplets in an Array

LeetCode Problem 2179 Difficulty: 🔴 Hard Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution Problem Understanding In this problem, we are given two arrays, nums1 and nums2 , each containing every integer from 0 to n - 1 exactly once. In other words, both arrays are permutations of the same set of values. We need to count how many triplets (x,...

Practice › LeetCode › LeetCode 25xx ›

LeetCode 2519 - Count the Number of K-Big Indices

LeetCode Problem 2519 Difficulty: 🔴 Hard Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution LeetCode 2519 - Count the Number of K-Big Indices Problem Understanding This problem asks us to determine how many indices in an array satisfy a very specific condition related to smaller values on both sides. For an index i to be considered k-big , two separate requirements...

Practice › LeetCode › LeetCode 31xx ›

LeetCode 3109 - Find the Index of Permutation

LeetCode Problem 3109 Difficulty: 🟡 Medium Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution Problem Understanding The problem gives us a permutation perm of the integers [1, 2, ..., n] . A permutation is simply an arrangement of all numbers from 1 to n where each number appears exactly once. We are asked to determine the lexicographic index of this permutation...

Practice › LeetCode › LeetCode 04xx ›

LeetCode 493 - Reverse Pairs

LeetCode Problem 493 Difficulty: 🔴 Hard Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution Problem Understanding The problem asks us to count how many pairs of indices (i, j) satisfy two conditions: i < j nums[i] > 2 * nums[j] These pairs are called reverse pairs. Unlike the classic inversion count problem, where we check whether nums[i] > nums[j] , this...

Practice › LeetCode › LeetCode 16xx ›

LeetCode 1649 - Create Sorted Array through Instructions

LeetCode Problem 1649 Difficulty: 🔴 Hard Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution Problem Understanding The problem asks us to simulate building a sorted array incrementally. We process the instructions array from left to right, and for each value, we insert it into a container called nums while maintaining sorted order. However, the actual insertion is not the difficult part....

Practice › LeetCode › LeetCode 01xx ›

LeetCode 148 - Sort List

LeetCode Problem 148 Difficulty: 🟡 Medium Topics: Linked List, Two Pointers, Divide and Conquer, Sorting, Merge Sort Solution Problem Understanding The problem asks us to sort a singly linked list in ascending order and return the head of the sorted list. The input is the head node of a linked list. Each node contains an integer value and a pointer to the next node. Unlike arrays, linked lists do not...

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...

Practice › LeetCode › LeetCode 00xx ›

LeetCode 23 - Merge k Sorted Lists

LeetCode Problem 23 Difficulty: 🔴 Hard Topics: Linked List, Divide and Conquer, Heap (Priority Queue), Merge Sort Solution Problem Understanding The problem gives us an array of k sorted linked lists. Each linked list is already sorted in ascending order, and our task is to combine all of them into one single sorted linked list. A linked list node contains a value and a pointer to the next node. The...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 315 - Count of Smaller Numbers After Self

LeetCode Problem 315 Difficulty: 🔴 Hard Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution Problem Understanding The problem asks us to compute, for every element in the array, how many elements to its right are strictly smaller than it. Given an array nums , we must return another array counts of the same length. For each index i , counts[i] represents...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 327 - Count of Range Sum

LeetCode Problem 327 Difficulty: 🔴 Hard Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution LeetCode 327 - Count of Range Sum Problem Understanding This problem asks us to count how many subarrays have sums that fall within a given inclusive range [lower, upper] . A range sum S(i, j) represents the sum of all elements from index i through index j...

Practice › LeetCode › LeetCode 20xx ›

LeetCode 2031 - Count Subarrays With More Ones Than Zeros

LeetCode Problem 2031 Difficulty: 🟡 Medium Topics: Array, Hash Table, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution Problem Understanding This problem asks us to count all subarrays of a binary array nums that contain more 1 s than 0 s. In other words, for any contiguous slice of the array, if the number of 1 s exceeds the number of 0 s,...

Practice › LeetCode › LeetCode (archived) › LeetCode 09xx ›

LeetCode 912: Sort an Array

Problem Restatement We are given an integer array nums . Return the array sorted in ascending order. The problem requires solving this without using built-in sorting functions, in O(n log n) time, with as little extra space as possible. Input and Output Item Meaning Input An integer array nums Output The same values sorted in ascending order Restriction Do not use built-in sorting functions Target time O(n log n) Function...

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 493: Reverse Pairs

Problem Restatement We are given an integer array nums . We need to count pairs of indices (i, j) such that: 0 <= i < j < nums.length and: nums[i] > 2 * nums[j] These are called reverse pairs. The input length can be up to 5 * 10^4 , and values may be negative or as large as 32-bit signed integers. Input and Output Item Meaning Input Integer array...

Practice › LeetCode › LeetCode (archived) › LeetCode 03xx ›

LeetCode 315: Count of Smaller Numbers After Self

Problem Restatement We are given an integer array nums . For each index i , count how many numbers to the right of nums[i] are smaller than nums[i] . Return an array counts , where: counts[i] = number of smaller elements to the right of nums[i] For example, in: nums = [5, 2, 6, 1] the answer is: [2, 1, 1, 0] because: Index Value Smaller values to the right...

Practice › LeetCode › LeetCode (archived) › LeetCode 01xx ›

LeetCode 148: Sort List

Problem Restatement We are given the head of a singly linked list. Return the list after sorting it in ascending order. The problem asks for an O(n log n) time solution. The follow-up asks whether we can sort the list with constant extra space. The number of nodes is in the range [0, 5 * 10^4] , and node values are between -10^5 and 10^5 . Examples Example 1: head...

Practice › LeetCode › LeetCode (archived) › LeetCode 03xx ›

LeetCode 327: Count of Range Sum

Problem Restatement We are given an integer array nums and two integers lower and upper . A range sum is the sum of a contiguous subarray: S(i, j) = nums[i] + nums[i + 1] + ... + nums[j] where i <= j . We need to count how many range sums lie inside this inclusive range: lower <= S(i, j) <= upper The naive O(n^2) solution is too slow, so...

Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.20 Inversion Counting

6.20 Inversion Counting An inversion is a pair of positions that appears in the opposite order from the final sorted order. Inversion counting measures how far an array is from being sorted. It is useful for ranking distance, sorting analysis, permutation comparison, and adaptive algorithm design. Problem You have an array A[0..n-1] . You want to count the number of pairs (i, j) such that: i < j and A[i]...

Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.4 Merge Sort

6.4 Merge Sort Merge sort is the standard example of divide and conquer sorting. It divides the input into two smaller arrays, sorts each half, and then merges the two sorted halves into one sorted output. The central operation is not the division step. It is the merge step, because merging is where the algorithm combines local order into global order. Problem You have an array A[0..n-1] . You want...

Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Balanced K Way Merge Sort

Balanced K Way Merge Sort Balanced k way merge sort is an external sorting algorithm that repeatedly merges sorted runs in groups of at most $k$. Unlike polyphase merge sort, it tries to keep the merge work evenly distributed across passes. It is a simple and common model for large file sorting. The input is first divided into memory-sized chunks, each chunk is sorted internally, and then the resulting sorted...

Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

GPU Merge Sort

GPU Merge Sort GPU merge sort adapts merge sort to GPU execution by replacing recursive merging with parallel merge kernels. The algorithm operates in passes, merging sorted runs of increasing size. Unlike GPU radix sort, this method works for arbitrary comparable keys. Its performance depends on efficient parallel merge and memory throughput. Problem Given an array $A$ of size $n$ stored on a GPU, sort it in nondecreasing order. Algorithm...

Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Adaptive Shivers Sort

Adaptive Shivers Sort Adaptive Shivers sort is a run-based merge sort that improves how runs are merged. It detects natural runs and applies a stack discipline with carefully chosen merge rules to keep merges balanced. You use it when input contains natural runs and you want tighter control over merge cost than simple strategies. Problem Given an array ( A ), sort it by: detecting natural runs merging them in...

Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Adaptive Merge Sort

Adaptive Merge Sort Adaptive merge sort improves standard merge sort by detecting existing order in the input. Instead of blindly splitting into fixed halves, it identifies already sorted subsequences called runs and merges them. You use it when the input often contains partial order. Problem Given an array ( A ) of size ( n ), sort it while taking advantage of any existing sorted segments. Idea If the array...

Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Top Down Merge Sort

Top Down Merge Sort Top down merge sort is the canonical recursive form of merge sort. It starts from the full array, splits it into halves recursively until single elements remain, then merges upward. This form directly follows the divide and conquer recurrence and is the most common presentation in textbooks. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots \le...

Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Block Merge Sort

Block Merge Sort Block merge sort is a stable merge sort variant designed to reduce auxiliary memory while keeping good practical performance. Instead of copying the whole array into a second array, it divides sorted ranges into blocks and rearranges those blocks before finishing with local merges. The algorithm is more complex than ordinary merge sort, but it gives an important tradeoff: stable sorting with less extra memory. Problem Given...

Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Merge Sort

Merge Sort Merge sort is a divide and conquer sorting algorithm. It splits the input into smaller parts, sorts each part recursively, then merges the sorted parts into a single sorted sequence. It guarantees stable ordering and predictable time complexity. It performs well on large datasets and external memory systems. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots \le A[n-1]...

Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Natural Runs Sort

Natural Runs Sort Natural runs sort is an adaptive sorting method that first finds sorted subsequences already present in the input. These subsequences are called natural runs. The algorithm then merges the runs until the whole sequence is sorted. You use it when input data often contains long ordered stretches. Problem Given an array ( A ) of size ( n ), sort it by exploiting existing non-decreasing regions. A...

Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

Parallel Merge Sort

Parallel Merge Sort Parallel merge sort extends merge sort by executing recursive subproblems concurrently. The structure remains divide and conquer, but the recursion tree becomes a parallel computation graph. You split the array into halves, sort each half in parallel, then merge the results. The merge step can also be parallelized using partitioning techniques. Problem Given an array $A$ of size $n$, produce a sorted array in nondecreasing order using...

Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Polyphase Merge Sort

Polyphase Merge Sort Polyphase merge sort is an external sorting algorithm for merging many sorted runs using a limited number of files or tapes. It avoids the rigid redistribution step used by balanced merge sort. Instead, it places different numbers of runs on different input files so each merge phase naturally prepares the next phase. This method was especially important for tape drives, where rewinding and redistribution were expensive. The...

Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

External Merge Sort

External Merge Sort External merge sort is a disk-based sorting algorithm designed for datasets that exceed main memory. It minimizes random I/O and relies on sequential reads and writes, which are efficient on disks and object storage. You use it when the input size is much larger than RAM, for example multi-gigabyte or terabyte scale data. Model Assume: Input size: $N$ elements Memory capacity: $M$ elements Block size: $B$ elements...

Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Natural Merge Sort

Natural Merge Sort Natural merge sort improves merge sort by exploiting existing order in the input. Instead of splitting blindly, it scans the array to find already sorted runs, then merges those runs. This approach adapts to partially sorted data and can reduce the number of passes. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots \le A[n-1] $$ Idea A...

Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Bottom Up Merge Sort

Bottom Up Merge Sort Bottom up merge sort removes recursion and builds the sorted array iteratively. It starts by treating each element as a sorted run of size one, then repeatedly merges adjacent runs of increasing size. This form improves control over memory access and avoids recursion overhead. It is commonly used in systems where stack usage must remain bounded. Problem Given an array $A$ of length $n$, reorder it...

Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Tape Merge Sort

Tape Merge Sort Tape merge sort is an external sorting algorithm designed for sequential storage. It was historically used with magnetic tapes, where random access was expensive or unavailable. The algorithm writes sorted runs to multiple tapes, then repeatedly merges runs from input tapes onto output tapes. The same idea still matters for sequential external storage: make long sequential reads and writes, avoid random seeks, and reduce the number of...

Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Tournament Merge Sort

Tournament Merge Sort Tournament merge sort uses a tournament tree to merge sorted sequences. Each element competes in a structured tree, and the winner at the root is the smallest element. After removing the winner, the tree is updated to find the next smallest. It is conceptually similar to multiway merge, but uses a tournament structure instead of a heap. Problem Given an array $A$ of length $n$, reorder it...

Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Cache Oblivious Merge Sort

Cache Oblivious Merge Sort Cache oblivious merge sort is a merge sort variant designed for memory hierarchies. It improves locality without knowing the cache size, block size, or number of cache levels. The algorithm uses recursive structure to make subproblems eventually fit into cache automatically. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots \le A[n-1] $$ while reducing cache misses...

Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Cascade Merge Sort

Cascade Merge Sort Cascade merge sort is an external sorting method that organizes merging into a pipeline of stages. Each stage merges a group of sorted runs and passes the resulting larger runs to the next stage. The purpose is to reduce repeated redistribution and make external merging easier to schedule. It is most useful when runs arrive gradually or when storage bandwidth can be used by several merge stages...

Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

In Place Merge Sort

In Place Merge Sort In place merge sort is a merge sort variant that tries to keep the extra memory small. Standard merge sort uses an auxiliary array of size $n$ during merging. In place merge sort instead merges two adjacent sorted ranges inside the original array. The main difficulty is the merge step. Splitting is easy, but merging two sorted adjacent ranges without a large buffer is more complex...

Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Cache Efficient Merge Sort

Cache Efficient Merge Sort Cache efficient merge sort improves merge sort by reducing cache misses. It reorganizes recursion and merging so that working data fits into cache levels. The goal is to minimize memory transfers rather than just comparisons. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots \le A[n-1] $$ while improving cache locality. Idea Standard merge sort performs well...

Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Multiway Merge Sort

Multiway Merge Sort Multiway merge sort generalizes merge sort by splitting the input into $k$ parts instead of two, and merging $k$ sorted sequences at each step. It is especially useful when merging cost dominates, such as in external memory or database systems. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots \le A[n-1] $$ Idea Instead of binary splitting: $$...

#merge-sort

LeetCode 3739 - Count Subarrays With Majority Element II

LeetCode 3737 - Count Subarrays With Majority Element I

LeetCode 2426 - Number of Pairs Satisfying Inequality

LeetCode 2179 - Count Good Triplets in an Array

LeetCode 2519 - Count the Number of K-Big Indices

LeetCode 3109 - Find the Index of Permutation

LeetCode 493 - Reverse Pairs

LeetCode 1649 - Create Sorted Array through Instructions

LeetCode 148 - Sort List

LeetCode 912 - Sort an Array

LeetCode 23 - Merge k Sorted Lists

LeetCode 315 - Count of Smaller Numbers After Self

LeetCode 327 - Count of Range Sum

LeetCode 2031 - Count Subarrays With More Ones Than Zeros

LeetCode 912: Sort an Array

LeetCode 493: Reverse Pairs

LeetCode 315: Count of Smaller Numbers After Self

LeetCode 148: Sort List

LeetCode 327: Count of Range Sum

6.20 Inversion Counting

6.4 Merge Sort

Balanced K Way Merge Sort

GPU Merge Sort

Adaptive Shivers Sort

Adaptive Merge Sort

Top Down Merge Sort

Block Merge Sort

Merge Sort

Natural Runs Sort

Parallel Merge Sort

Polyphase Merge Sort

External Merge Sort

Natural Merge Sort

Bottom Up Merge Sort

Tape Merge Sort

Tournament Merge Sort

Cache Oblivious Merge Sort

Cascade Merge Sort

In Place Merge Sort

Cache Efficient Merge Sort

Multiway Merge Sort