func mergeSort(nums []int) []int {
}func mergeSort(nums []int) []int {
// Base case: a slice of length 0 or 1 is already sorted — nothing to do.
}func mergeSort(nums []int) []int {
// Base case: a slice of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1 {
return nums
}
}func mergeSort(nums []int) []int {
// Base case: a slice of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1 {
return nums
}
// Divide: split down the middle and sort each half recursively.
}func mergeSort(nums []int) []int {
// Base case: a slice of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1 {
return nums
}
// Divide: split down the middle and sort each half recursively.
mid := len(nums) / 2
left := mergeSort(nums[:mid])
right := mergeSort(nums[mid:])
}func mergeSort(nums []int) []int {
// Base case: a slice of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1 {
return nums
}
// Divide: split down the middle and sort each half recursively.
mid := len(nums) / 2
left := mergeSort(nums[:mid])
right := mergeSort(nums[mid:])
// Conquer: both halves are sorted, so merge them into one sorted slice.
}func mergeSort(nums []int) []int {
// Base case: a slice of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1 {
return nums
}
// Divide: split down the middle and sort each half recursively.
mid := len(nums) / 2
left := mergeSort(nums[:mid])
right := mergeSort(nums[mid:])
// Conquer: both halves are sorted, so merge them into one sorted slice.
return merge(left, right)
}func mergeSort(nums []int) []int {
// Base case: a slice of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1 {
return nums
}
// Divide: split down the middle and sort each half recursively.
mid := len(nums) / 2
left := mergeSort(nums[:mid])
right := mergeSort(nums[mid:])
// Conquer: both halves are sorted, so merge them into one sorted slice.
return merge(left, right)
}
// merge combines two already-sorted slices into one sorted slice.
// Preallocate the exact capacity, and give each input its own read index.func mergeSort(nums []int) []int {
// Base case: a slice of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1 {
return nums
}
// Divide: split down the middle and sort each half recursively.
mid := len(nums) / 2
left := mergeSort(nums[:mid])
right := mergeSort(nums[mid:])
// Conquer: both halves are sorted, so merge them into one sorted slice.
return merge(left, right)
}
// merge combines two already-sorted slices into one sorted slice.
func merge(a, b []int) []int {
// Preallocate the exact capacity, and give each input its own read index.
res := make([]int, 0, len(a)+len(b))
i, j := 0, 0
}func mergeSort(nums []int) []int {
// Base case: a slice of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1 {
return nums
}
// Divide: split down the middle and sort each half recursively.
mid := len(nums) / 2
left := mergeSort(nums[:mid])
right := mergeSort(nums[mid:])
// Conquer: both halves are sorted, so merge them into one sorted slice.
return merge(left, right)
}
// merge combines two already-sorted slices into one sorted slice.
func merge(a, b []int) []int {
// Preallocate the exact capacity, and give each input its own read index.
res := make([]int, 0, len(a)+len(b))
i, j := 0, 0
// While both still have elements, compare their fronts and take the smaller.
}func mergeSort(nums []int) []int {
// Base case: a slice of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1 {
return nums
}
// Divide: split down the middle and sort each half recursively.
mid := len(nums) / 2
left := mergeSort(nums[:mid])
right := mergeSort(nums[mid:])
// Conquer: both halves are sorted, so merge them into one sorted slice.
return merge(left, right)
}
// merge combines two already-sorted slices into one sorted slice.
func merge(a, b []int) []int {
// Preallocate the exact capacity, and give each input its own read index.
res := make([]int, 0, len(a)+len(b))
i, j := 0, 0
// While both still have elements, compare their fronts and take the smaller.
for i < len(a) && j < len(b) {
}
}func mergeSort(nums []int) []int {
// Base case: a slice of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1 {
return nums
}
// Divide: split down the middle and sort each half recursively.
mid := len(nums) / 2
left := mergeSort(nums[:mid])
right := mergeSort(nums[mid:])
// Conquer: both halves are sorted, so merge them into one sorted slice.
return merge(left, right)
}
// merge combines two already-sorted slices into one sorted slice.
func merge(a, b []int) []int {
// Preallocate the exact capacity, and give each input its own read index.
res := make([]int, 0, len(a)+len(b))
i, j := 0, 0
// While both still have elements, compare their fronts and take the smaller.
for i < len(a) && j < len(b) {
// Using <= (not <) keeps equal elements in their original order — stable.
}
}func mergeSort(nums []int) []int {
// Base case: a slice of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1 {
return nums
}
// Divide: split down the middle and sort each half recursively.
mid := len(nums) / 2
left := mergeSort(nums[:mid])
right := mergeSort(nums[mid:])
// Conquer: both halves are sorted, so merge them into one sorted slice.
return merge(left, right)
}
// merge combines two already-sorted slices into one sorted slice.
func merge(a, b []int) []int {
// Preallocate the exact capacity, and give each input its own read index.
res := make([]int, 0, len(a)+len(b))
i, j := 0, 0
// While both still have elements, compare their fronts and take the smaller.
for i < len(a) && j < len(b) {
// Using <= (not <) keeps equal elements in their original order — stable.
if a[i] <= b[j] {
res = append(res, a[i])
i++
} else {
res = append(res, b[j])
j++
}
}
}func mergeSort(nums []int) []int {
// Base case: a slice of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1 {
return nums
}
// Divide: split down the middle and sort each half recursively.
mid := len(nums) / 2
left := mergeSort(nums[:mid])
right := mergeSort(nums[mid:])
// Conquer: both halves are sorted, so merge them into one sorted slice.
return merge(left, right)
}
// merge combines two already-sorted slices into one sorted slice.
func merge(a, b []int) []int {
// Preallocate the exact capacity, and give each input its own read index.
res := make([]int, 0, len(a)+len(b))
i, j := 0, 0
// While both still have elements, compare their fronts and take the smaller.
for i < len(a) && j < len(b) {
// Using <= (not <) keeps equal elements in their original order — stable.
if a[i] <= b[j] {
res = append(res, a[i])
i++
} else {
res = append(res, b[j])
j++
}
}
// Exactly one side has leftovers (already sorted); append them as-is.
}func mergeSort(nums []int) []int {
// Base case: a slice of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1 {
return nums
}
// Divide: split down the middle and sort each half recursively.
mid := len(nums) / 2
left := mergeSort(nums[:mid])
right := mergeSort(nums[mid:])
// Conquer: both halves are sorted, so merge them into one sorted slice.
return merge(left, right)
}
// merge combines two already-sorted slices into one sorted slice.
func merge(a, b []int) []int {
// Preallocate the exact capacity, and give each input its own read index.
res := make([]int, 0, len(a)+len(b))
i, j := 0, 0
// While both still have elements, compare their fronts and take the smaller.
for i < len(a) && j < len(b) {
// Using <= (not <) keeps equal elements in their original order — stable.
if a[i] <= b[j] {
res = append(res, a[i])
i++
} else {
res = append(res, b[j])
j++
}
}
// Exactly one side has leftovers (already sorted); append them as-is.
res = append(res, a[i:]...)
res = append(res, b[j:]...)
return res
}def merge_sort(nums):
passdef merge_sort(nums):
# Base case: a list of length 0 or 1 is already sorted — nothing to do.
passdef merge_sort(nums):
# Base case: a list of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1:
return numsdef merge_sort(nums):
# Base case: a list of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1:
return nums
# Divide: split down the middle and sort each half recursively.def merge_sort(nums):
# Base case: a list of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1:
return nums
# Divide: split down the middle and sort each half recursively.
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])def merge_sort(nums):
# Base case: a list of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1:
return nums
# Divide: split down the middle and sort each half recursively.
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
# Conquer: both halves are sorted, so merge them into one sorted list.def merge_sort(nums):
# Base case: a list of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1:
return nums
# Divide: split down the middle and sort each half recursively.
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
# Conquer: both halves are sorted, so merge them into one sorted list.
return merge(left, right)def merge_sort(nums):
# Base case: a list of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1:
return nums
# Divide: split down the middle and sort each half recursively.
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
# Conquer: both halves are sorted, so merge them into one sorted list.
return merge(left, right)
# merge combines two already-sorted lists into one sorted list.
# Start with an empty result, and give each input its own read index.def merge_sort(nums):
# Base case: a list of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1:
return nums
# Divide: split down the middle and sort each half recursively.
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
# Conquer: both halves are sorted, so merge them into one sorted list.
return merge(left, right)
# merge combines two already-sorted lists into one sorted list.
def merge(a, b):
# Start with an empty result, and give each input its own read index.
res = []
i, j = 0, 0def merge_sort(nums):
# Base case: a list of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1:
return nums
# Divide: split down the middle and sort each half recursively.
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
# Conquer: both halves are sorted, so merge them into one sorted list.
return merge(left, right)
# merge combines two already-sorted lists into one sorted list.
def merge(a, b):
# Start with an empty result, and give each input its own read index.
res = []
i, j = 0, 0
# While both still have elements, compare their fronts and take the smaller.def merge_sort(nums):
# Base case: a list of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1:
return nums
# Divide: split down the middle and sort each half recursively.
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
# Conquer: both halves are sorted, so merge them into one sorted list.
return merge(left, right)
# merge combines two already-sorted lists into one sorted list.
def merge(a, b):
# Start with an empty result, and give each input its own read index.
res = []
i, j = 0, 0
# While both still have elements, compare their fronts and take the smaller.
while i < len(a) and j < len(b):
passdef merge_sort(nums):
# Base case: a list of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1:
return nums
# Divide: split down the middle and sort each half recursively.
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
# Conquer: both halves are sorted, so merge them into one sorted list.
return merge(left, right)
# merge combines two already-sorted lists into one sorted list.
def merge(a, b):
# Start with an empty result, and give each input its own read index.
res = []
i, j = 0, 0
# While both still have elements, compare their fronts and take the smaller.
while i < len(a) and j < len(b):
# Using <= (not <) keeps equal elements in their original order — stable.
passdef merge_sort(nums):
# Base case: a list of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1:
return nums
# Divide: split down the middle and sort each half recursively.
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
# Conquer: both halves are sorted, so merge them into one sorted list.
return merge(left, right)
# merge combines two already-sorted lists into one sorted list.
def merge(a, b):
# Start with an empty result, and give each input its own read index.
res = []
i, j = 0, 0
# While both still have elements, compare their fronts and take the smaller.
while i < len(a) and j < len(b):
# Using <= (not <) keeps equal elements in their original order — stable.
if a[i] <= b[j]:
res.append(a[i])
i += 1
else:
res.append(b[j])
j += 1def merge_sort(nums):
# Base case: a list of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1:
return nums
# Divide: split down the middle and sort each half recursively.
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
# Conquer: both halves are sorted, so merge them into one sorted list.
return merge(left, right)
# merge combines two already-sorted lists into one sorted list.
def merge(a, b):
# Start with an empty result, and give each input its own read index.
res = []
i, j = 0, 0
# While both still have elements, compare their fronts and take the smaller.
while i < len(a) and j < len(b):
# Using <= (not <) keeps equal elements in their original order — stable.
if a[i] <= b[j]:
res.append(a[i])
i += 1
else:
res.append(b[j])
j += 1
# Exactly one side has leftovers (already sorted); append them as-is.def merge_sort(nums):
# Base case: a list of length 0 or 1 is already sorted — nothing to do.
if len(nums) <= 1:
return nums
# Divide: split down the middle and sort each half recursively.
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
# Conquer: both halves are sorted, so merge them into one sorted list.
return merge(left, right)
# merge combines two already-sorted lists into one sorted list.
def merge(a, b):
# Start with an empty result, and give each input its own read index.
res = []
i, j = 0, 0
# While both still have elements, compare their fronts and take the smaller.
while i < len(a) and j < len(b):
# Using <= (not <) keeps equal elements in their original order — stable.
if a[i] <= b[j]:
res.append(a[i])
i += 1
else:
res.append(b[j])
j += 1
# Exactly one side has leftovers (already sorted); append them as-is.
res.extend(a[i:])
res.extend(b[j:])
return resfunction mergeSort(nums) {
}function mergeSort(nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
}function mergeSort(nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
}function mergeSort(nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
}function mergeSort(nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
}function mergeSort(nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
// Conquer: both halves are sorted, so merge them into one sorted array.
}function mergeSort(nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}function mergeSort(nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
// Start with an empty result, and give each input its own read index.
function mergeSort(nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
function merge(a, b) {
// Start with an empty result, and give each input its own read index.
const res = [];
let i = 0, j = 0;
}function mergeSort(nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
function merge(a, b) {
// Start with an empty result, and give each input its own read index.
const res = [];
let i = 0, j = 0;
// While both still have elements, compare their fronts and take the smaller.
}function mergeSort(nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
function merge(a, b) {
// Start with an empty result, and give each input its own read index.
const res = [];
let i = 0, j = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.length && j < b.length) {
}
}function mergeSort(nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
function merge(a, b) {
// Start with an empty result, and give each input its own read index.
const res = [];
let i = 0, j = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.length && j < b.length) {
// Using <= (not <) keeps equal elements in their original order — stable.
}
}function mergeSort(nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
function merge(a, b) {
// Start with an empty result, and give each input its own read index.
const res = [];
let i = 0, j = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.length && j < b.length) {
// Using <= (not <) keeps equal elements in their original order — stable.
if (a[i] <= b[j]) {
res.push(a[i]);
i++;
} else {
res.push(b[j]);
j++;
}
}
}function mergeSort(nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
function merge(a, b) {
// Start with an empty result, and give each input its own read index.
const res = [];
let i = 0, j = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.length && j < b.length) {
// Using <= (not <) keeps equal elements in their original order — stable.
if (a[i] <= b[j]) {
res.push(a[i]);
i++;
} else {
res.push(b[j]);
j++;
}
}
// Exactly one side has leftovers (already sorted); append them as-is.
}function mergeSort(nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
function merge(a, b) {
// Start with an empty result, and give each input its own read index.
const res = [];
let i = 0, j = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.length && j < b.length) {
// Using <= (not <) keeps equal elements in their original order — stable.
if (a[i] <= b[j]) {
res.push(a[i]);
i++;
} else {
res.push(b[j]);
j++;
}
}
// Exactly one side has leftovers (already sorted); append them as-is.
return res.concat(a.slice(i), b.slice(j));
}function mergeSort(nums: number[]): number[] {
}function mergeSort(nums: number[]): number[] {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
}function mergeSort(nums: number[]): number[] {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
}function mergeSort(nums: number[]): number[] {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
}function mergeSort(nums: number[]): number[] {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
}function mergeSort(nums: number[]): number[] {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
// Conquer: both halves are sorted, so merge them into one sorted array.
}function mergeSort(nums: number[]): number[] {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}function mergeSort(nums: number[]): number[] {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
// Start with an empty result, and give each input its own read index.
function mergeSort(nums: number[]): number[] {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
function merge(a: number[], b: number[]): number[] {
// Start with an empty result, and give each input its own read index.
const res: number[] = [];
let i = 0, j = 0;
}function mergeSort(nums: number[]): number[] {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
function merge(a: number[], b: number[]): number[] {
// Start with an empty result, and give each input its own read index.
const res: number[] = [];
let i = 0, j = 0;
// While both still have elements, compare their fronts and take the smaller.
}function mergeSort(nums: number[]): number[] {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
function merge(a: number[], b: number[]): number[] {
// Start with an empty result, and give each input its own read index.
const res: number[] = [];
let i = 0, j = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.length && j < b.length) {
}
}function mergeSort(nums: number[]): number[] {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
function merge(a: number[], b: number[]): number[] {
// Start with an empty result, and give each input its own read index.
const res: number[] = [];
let i = 0, j = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.length && j < b.length) {
// Using <= (not <) keeps equal elements in their original order — stable.
}
}function mergeSort(nums: number[]): number[] {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
function merge(a: number[], b: number[]): number[] {
// Start with an empty result, and give each input its own read index.
const res: number[] = [];
let i = 0, j = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.length && j < b.length) {
// Using <= (not <) keeps equal elements in their original order — stable.
if (a[i] <= b[j]) {
res.push(a[i]);
i++;
} else {
res.push(b[j]);
j++;
}
}
}function mergeSort(nums: number[]): number[] {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
function merge(a: number[], b: number[]): number[] {
// Start with an empty result, and give each input its own read index.
const res: number[] = [];
let i = 0, j = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.length && j < b.length) {
// Using <= (not <) keeps equal elements in their original order — stable.
if (a[i] <= b[j]) {
res.push(a[i]);
i++;
} else {
res.push(b[j]);
j++;
}
}
// Exactly one side has leftovers (already sorted); append them as-is.
}function mergeSort(nums: number[]): number[] {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
function merge(a: number[], b: number[]): number[] {
// Start with an empty result, and give each input its own read index.
const res: number[] = [];
let i = 0, j = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.length && j < b.length) {
// Using <= (not <) keeps equal elements in their original order — stable.
if (a[i] <= b[j]) {
res.push(a[i]);
i++;
} else {
res.push(b[j]);
j++;
}
}
// Exactly one side has leftovers (already sorted); append them as-is.
return res.concat(a.slice(i), b.slice(j));
}import java.util.Arrays;
class Solution {
static int[] mergeSort(int[] nums) {
}
}import java.util.Arrays;
class Solution {
static int[] mergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
}
}import java.util.Arrays;
class Solution {
static int[] mergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
}
}import java.util.Arrays;
class Solution {
static int[] mergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
}
}import java.util.Arrays;
class Solution {
static int[] mergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = nums.length / 2;
int[] left = mergeSort(Arrays.copyOfRange(nums, 0, mid));
int[] right = mergeSort(Arrays.copyOfRange(nums, mid, nums.length));
}
}import java.util.Arrays;
class Solution {
static int[] mergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = nums.length / 2;
int[] left = mergeSort(Arrays.copyOfRange(nums, 0, mid));
int[] right = mergeSort(Arrays.copyOfRange(nums, mid, nums.length));
// Conquer: both halves are sorted, so merge them into one sorted array.
}
}import java.util.Arrays;
class Solution {
static int[] mergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = nums.length / 2;
int[] left = mergeSort(Arrays.copyOfRange(nums, 0, mid));
int[] right = mergeSort(Arrays.copyOfRange(nums, mid, nums.length));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
}import java.util.Arrays;
class Solution {
static int[] mergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = nums.length / 2;
int[] left = mergeSort(Arrays.copyOfRange(nums, 0, mid));
int[] right = mergeSort(Arrays.copyOfRange(nums, mid, nums.length));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
// Allocate the exact size: a and b get read indexes, res a write index.
}import java.util.Arrays;
class Solution {
static int[] mergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = nums.length / 2;
int[] left = mergeSort(Arrays.copyOfRange(nums, 0, mid));
int[] right = mergeSort(Arrays.copyOfRange(nums, mid, nums.length));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
private static int[] merge(int[] a, int[] b) {
// Allocate the exact size: a and b get read indexes, res a write index.
int[] res = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
}
}import java.util.Arrays;
class Solution {
static int[] mergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = nums.length / 2;
int[] left = mergeSort(Arrays.copyOfRange(nums, 0, mid));
int[] right = mergeSort(Arrays.copyOfRange(nums, mid, nums.length));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
private static int[] merge(int[] a, int[] b) {
// Allocate the exact size: a and b get read indexes, res a write index.
int[] res = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
// While both still have elements, compare their fronts and take the smaller.
}
}import java.util.Arrays;
class Solution {
static int[] mergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = nums.length / 2;
int[] left = mergeSort(Arrays.copyOfRange(nums, 0, mid));
int[] right = mergeSort(Arrays.copyOfRange(nums, mid, nums.length));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
private static int[] merge(int[] a, int[] b) {
// Allocate the exact size: a and b get read indexes, res a write index.
int[] res = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.length && j < b.length) {
}
}
}import java.util.Arrays;
class Solution {
static int[] mergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = nums.length / 2;
int[] left = mergeSort(Arrays.copyOfRange(nums, 0, mid));
int[] right = mergeSort(Arrays.copyOfRange(nums, mid, nums.length));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
private static int[] merge(int[] a, int[] b) {
// Allocate the exact size: a and b get read indexes, res a write index.
int[] res = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.length && j < b.length) {
// Using <= (not <) keeps equal elements in their original order — stable.
}
}
}import java.util.Arrays;
class Solution {
static int[] mergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = nums.length / 2;
int[] left = mergeSort(Arrays.copyOfRange(nums, 0, mid));
int[] right = mergeSort(Arrays.copyOfRange(nums, mid, nums.length));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
private static int[] merge(int[] a, int[] b) {
// Allocate the exact size: a and b get read indexes, res a write index.
int[] res = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.length && j < b.length) {
// Using <= (not <) keeps equal elements in their original order — stable.
if (a[i] <= b[j]) {
res[k++] = a[i++];
} else {
res[k++] = b[j++];
}
}
}
}import java.util.Arrays;
class Solution {
static int[] mergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = nums.length / 2;
int[] left = mergeSort(Arrays.copyOfRange(nums, 0, mid));
int[] right = mergeSort(Arrays.copyOfRange(nums, mid, nums.length));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
private static int[] merge(int[] a, int[] b) {
// Allocate the exact size: a and b get read indexes, res a write index.
int[] res = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.length && j < b.length) {
// Using <= (not <) keeps equal elements in their original order — stable.
if (a[i] <= b[j]) {
res[k++] = a[i++];
} else {
res[k++] = b[j++];
}
}
// Exactly one side has leftovers (already sorted); copy them as-is.
}
}import java.util.Arrays;
class Solution {
static int[] mergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = nums.length / 2;
int[] left = mergeSort(Arrays.copyOfRange(nums, 0, mid));
int[] right = mergeSort(Arrays.copyOfRange(nums, mid, nums.length));
// Conquer: both halves are sorted, so merge them into one sorted array.
return merge(left, right);
}
// merge combines two already-sorted arrays into one sorted array.
private static int[] merge(int[] a, int[] b) {
// Allocate the exact size: a and b get read indexes, res a write index.
int[] res = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.length && j < b.length) {
// Using <= (not <) keeps equal elements in their original order — stable.
if (a[i] <= b[j]) {
res[k++] = a[i++];
} else {
res[k++] = b[j++];
}
}
// Exactly one side has leftovers (already sorted); copy them as-is.
while (i < a.length) {
res[k++] = a[i++];
}
while (j < b.length) {
res[k++] = b[j++];
}
return res;
}
}using System;
public class Solution {
public static int[] MergeSort(int[] nums) {
}
}using System;
public class Solution {
public static int[] MergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
}
}using System;
public class Solution {
public static int[] MergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.Length <= 1) {
return nums;
}
}
}using System;
public class Solution {
public static int[] MergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.Length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
}
}using System;
public class Solution {
public static int[] MergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.Length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = nums.Length / 2;
int[] left = MergeSort(nums[..mid]);
int[] right = MergeSort(nums[mid..]);
}
}using System;
public class Solution {
public static int[] MergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.Length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = nums.Length / 2;
int[] left = MergeSort(nums[..mid]);
int[] right = MergeSort(nums[mid..]);
// Conquer: both halves are sorted, so merge them into one sorted array.
}
}using System;
public class Solution {
public static int[] MergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.Length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = nums.Length / 2;
int[] left = MergeSort(nums[..mid]);
int[] right = MergeSort(nums[mid..]);
// Conquer: both halves are sorted, so merge them into one sorted array.
return Merge(left, right);
}
}using System;
public class Solution {
public static int[] MergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.Length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = nums.Length / 2;
int[] left = MergeSort(nums[..mid]);
int[] right = MergeSort(nums[mid..]);
// Conquer: both halves are sorted, so merge them into one sorted array.
return Merge(left, right);
}
// Merge combines two already-sorted arrays into one sorted array.
// Allocate the exact size: a and b get read indexes, res a write index.
}using System;
public class Solution {
public static int[] MergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.Length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = nums.Length / 2;
int[] left = MergeSort(nums[..mid]);
int[] right = MergeSort(nums[mid..]);
// Conquer: both halves are sorted, so merge them into one sorted array.
return Merge(left, right);
}
// Merge combines two already-sorted arrays into one sorted array.
private static int[] Merge(int[] a, int[] b) {
// Allocate the exact size: a and b get read indexes, res a write index.
int[] res = new int[a.Length + b.Length];
int i = 0, j = 0, k = 0;
}
}using System;
public class Solution {
public static int[] MergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.Length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = nums.Length / 2;
int[] left = MergeSort(nums[..mid]);
int[] right = MergeSort(nums[mid..]);
// Conquer: both halves are sorted, so merge them into one sorted array.
return Merge(left, right);
}
// Merge combines two already-sorted arrays into one sorted array.
private static int[] Merge(int[] a, int[] b) {
// Allocate the exact size: a and b get read indexes, res a write index.
int[] res = new int[a.Length + b.Length];
int i = 0, j = 0, k = 0;
// While both still have elements, compare their fronts and take the smaller.
}
}using System;
public class Solution {
public static int[] MergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.Length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = nums.Length / 2;
int[] left = MergeSort(nums[..mid]);
int[] right = MergeSort(nums[mid..]);
// Conquer: both halves are sorted, so merge them into one sorted array.
return Merge(left, right);
}
// Merge combines two already-sorted arrays into one sorted array.
private static int[] Merge(int[] a, int[] b) {
// Allocate the exact size: a and b get read indexes, res a write index.
int[] res = new int[a.Length + b.Length];
int i = 0, j = 0, k = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.Length && j < b.Length) {
}
}
}using System;
public class Solution {
public static int[] MergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.Length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = nums.Length / 2;
int[] left = MergeSort(nums[..mid]);
int[] right = MergeSort(nums[mid..]);
// Conquer: both halves are sorted, so merge them into one sorted array.
return Merge(left, right);
}
// Merge combines two already-sorted arrays into one sorted array.
private static int[] Merge(int[] a, int[] b) {
// Allocate the exact size: a and b get read indexes, res a write index.
int[] res = new int[a.Length + b.Length];
int i = 0, j = 0, k = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.Length && j < b.Length) {
// Using <= (not <) keeps equal elements in their original order — stable.
}
}
}using System;
public class Solution {
public static int[] MergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.Length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = nums.Length / 2;
int[] left = MergeSort(nums[..mid]);
int[] right = MergeSort(nums[mid..]);
// Conquer: both halves are sorted, so merge them into one sorted array.
return Merge(left, right);
}
// Merge combines two already-sorted arrays into one sorted array.
private static int[] Merge(int[] a, int[] b) {
// Allocate the exact size: a and b get read indexes, res a write index.
int[] res = new int[a.Length + b.Length];
int i = 0, j = 0, k = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.Length && j < b.Length) {
// Using <= (not <) keeps equal elements in their original order — stable.
if (a[i] <= b[j]) {
res[k++] = a[i++];
} else {
res[k++] = b[j++];
}
}
}
}using System;
public class Solution {
public static int[] MergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.Length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = nums.Length / 2;
int[] left = MergeSort(nums[..mid]);
int[] right = MergeSort(nums[mid..]);
// Conquer: both halves are sorted, so merge them into one sorted array.
return Merge(left, right);
}
// Merge combines two already-sorted arrays into one sorted array.
private static int[] Merge(int[] a, int[] b) {
// Allocate the exact size: a and b get read indexes, res a write index.
int[] res = new int[a.Length + b.Length];
int i = 0, j = 0, k = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.Length && j < b.Length) {
// Using <= (not <) keeps equal elements in their original order — stable.
if (a[i] <= b[j]) {
res[k++] = a[i++];
} else {
res[k++] = b[j++];
}
}
// Exactly one side has leftovers (already sorted); copy them as-is.
}
}using System;
public class Solution {
public static int[] MergeSort(int[] nums) {
// Base case: an array of length 0 or 1 is already sorted — nothing to do.
if (nums.Length <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = nums.Length / 2;
int[] left = MergeSort(nums[..mid]);
int[] right = MergeSort(nums[mid..]);
// Conquer: both halves are sorted, so merge them into one sorted array.
return Merge(left, right);
}
// Merge combines two already-sorted arrays into one sorted array.
private static int[] Merge(int[] a, int[] b) {
// Allocate the exact size: a and b get read indexes, res a write index.
int[] res = new int[a.Length + b.Length];
int i = 0, j = 0, k = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.Length && j < b.Length) {
// Using <= (not <) keeps equal elements in their original order — stable.
if (a[i] <= b[j]) {
res[k++] = a[i++];
} else {
res[k++] = b[j++];
}
}
// Exactly one side has leftovers (already sorted); copy them as-is.
while (i < a.Length) {
res[k++] = a[i++];
}
while (j < b.Length) {
res[k++] = b[j++];
}
return res;
}
}#include <stdlib.h>
#include <string.h>
// Declared up front so mergeSort can call it before it is defined further down.
static void merge(int* a, int an, int* b, int bn, int* out);
// Sorts nums[0..n) into out[0..n); out must have room for n ints.
void mergeSort(int* nums, int n, int* out) {
}#include <stdlib.h>
#include <string.h>
// Declared up front so mergeSort can call it before it is defined further down.
static void merge(int* a, int an, int* b, int bn, int* out);
// Sorts nums[0..n) into out[0..n); out must have room for n ints.
void mergeSort(int* nums, int n, int* out) {
// Base case: 0 or 1 element is already sorted — nothing to do.
}#include <stdlib.h>
#include <string.h>
// Declared up front so mergeSort can call it before it is defined further down.
static void merge(int* a, int an, int* b, int bn, int* out);
// Sorts nums[0..n) into out[0..n); out must have room for n ints.
void mergeSort(int* nums, int n, int* out) {
// Base case: 0 or 1 element is already sorted — nothing to do.
if (n <= 1) {
memcpy(out, nums, (size_t)n * sizeof(int));
return;
}
}#include <stdlib.h>
#include <string.h>
// Declared up front so mergeSort can call it before it is defined further down.
static void merge(int* a, int an, int* b, int bn, int* out);
// Sorts nums[0..n) into out[0..n); out must have room for n ints.
void mergeSort(int* nums, int n, int* out) {
// Base case: 0 or 1 element is already sorted — nothing to do.
if (n <= 1) {
memcpy(out, nums, (size_t)n * sizeof(int));
return;
}
// Divide: split down the middle and sort each half recursively.
}#include <stdlib.h>
#include <string.h>
// Declared up front so mergeSort can call it before it is defined further down.
static void merge(int* a, int an, int* b, int bn, int* out);
// Sorts nums[0..n) into out[0..n); out must have room for n ints.
void mergeSort(int* nums, int n, int* out) {
// Base case: 0 or 1 element is already sorted — nothing to do.
if (n <= 1) {
memcpy(out, nums, (size_t)n * sizeof(int));
return;
}
// Divide: split down the middle and sort each half recursively.
int mid = n / 2;
int* left = malloc((size_t)mid * sizeof(int));
int* right = malloc((size_t)(n - mid) * sizeof(int));
mergeSort(nums, mid, left);
mergeSort(nums + mid, n - mid, right);
}#include <stdlib.h>
#include <string.h>
// Declared up front so mergeSort can call it before it is defined further down.
static void merge(int* a, int an, int* b, int bn, int* out);
// Sorts nums[0..n) into out[0..n); out must have room for n ints.
void mergeSort(int* nums, int n, int* out) {
// Base case: 0 or 1 element is already sorted — nothing to do.
if (n <= 1) {
memcpy(out, nums, (size_t)n * sizeof(int));
return;
}
// Divide: split down the middle and sort each half recursively.
int mid = n / 2;
int* left = malloc((size_t)mid * sizeof(int));
int* right = malloc((size_t)(n - mid) * sizeof(int));
mergeSort(nums, mid, left);
mergeSort(nums + mid, n - mid, right);
// Conquer: both halves are sorted, so merge them into out.
}#include <stdlib.h>
#include <string.h>
// Declared up front so mergeSort can call it before it is defined further down.
static void merge(int* a, int an, int* b, int bn, int* out);
// Sorts nums[0..n) into out[0..n); out must have room for n ints.
void mergeSort(int* nums, int n, int* out) {
// Base case: 0 or 1 element is already sorted — nothing to do.
if (n <= 1) {
memcpy(out, nums, (size_t)n * sizeof(int));
return;
}
// Divide: split down the middle and sort each half recursively.
int mid = n / 2;
int* left = malloc((size_t)mid * sizeof(int));
int* right = malloc((size_t)(n - mid) * sizeof(int));
mergeSort(nums, mid, left);
mergeSort(nums + mid, n - mid, right);
// Conquer: both halves are sorted, so merge them into out.
merge(left, mid, right, n - mid, out);
free(left);
free(right);
}#include <stdlib.h>
#include <string.h>
// Declared up front so mergeSort can call it before it is defined further down.
static void merge(int* a, int an, int* b, int bn, int* out);
// Sorts nums[0..n) into out[0..n); out must have room for n ints.
void mergeSort(int* nums, int n, int* out) {
// Base case: 0 or 1 element is already sorted — nothing to do.
if (n <= 1) {
memcpy(out, nums, (size_t)n * sizeof(int));
return;
}
// Divide: split down the middle and sort each half recursively.
int mid = n / 2;
int* left = malloc((size_t)mid * sizeof(int));
int* right = malloc((size_t)(n - mid) * sizeof(int));
mergeSort(nums, mid, left);
mergeSort(nums + mid, n - mid, right);
// Conquer: both halves are sorted, so merge them into out.
merge(left, mid, right, n - mid, out);
free(left);
free(right);
}
// merge combines two already-sorted arrays into out.
// Each input gets a read index; out gets a write index.
#include <stdlib.h>
#include <string.h>
// Declared up front so mergeSort can call it before it is defined further down.
static void merge(int* a, int an, int* b, int bn, int* out);
// Sorts nums[0..n) into out[0..n); out must have room for n ints.
void mergeSort(int* nums, int n, int* out) {
// Base case: 0 or 1 element is already sorted — nothing to do.
if (n <= 1) {
memcpy(out, nums, (size_t)n * sizeof(int));
return;
}
// Divide: split down the middle and sort each half recursively.
int mid = n / 2;
int* left = malloc((size_t)mid * sizeof(int));
int* right = malloc((size_t)(n - mid) * sizeof(int));
mergeSort(nums, mid, left);
mergeSort(nums + mid, n - mid, right);
// Conquer: both halves are sorted, so merge them into out.
merge(left, mid, right, n - mid, out);
free(left);
free(right);
}
// merge combines two already-sorted arrays into out.
static void merge(int* a, int an, int* b, int bn, int* out) {
// Each input gets a read index; out gets a write index.
int i = 0, j = 0, k = 0;
}#include <stdlib.h>
#include <string.h>
// Declared up front so mergeSort can call it before it is defined further down.
static void merge(int* a, int an, int* b, int bn, int* out);
// Sorts nums[0..n) into out[0..n); out must have room for n ints.
void mergeSort(int* nums, int n, int* out) {
// Base case: 0 or 1 element is already sorted — nothing to do.
if (n <= 1) {
memcpy(out, nums, (size_t)n * sizeof(int));
return;
}
// Divide: split down the middle and sort each half recursively.
int mid = n / 2;
int* left = malloc((size_t)mid * sizeof(int));
int* right = malloc((size_t)(n - mid) * sizeof(int));
mergeSort(nums, mid, left);
mergeSort(nums + mid, n - mid, right);
// Conquer: both halves are sorted, so merge them into out.
merge(left, mid, right, n - mid, out);
free(left);
free(right);
}
// merge combines two already-sorted arrays into out.
static void merge(int* a, int an, int* b, int bn, int* out) {
// Each input gets a read index; out gets a write index.
int i = 0, j = 0, k = 0;
// While both still have elements, compare their fronts and take the smaller.
}#include <stdlib.h>
#include <string.h>
// Declared up front so mergeSort can call it before it is defined further down.
static void merge(int* a, int an, int* b, int bn, int* out);
// Sorts nums[0..n) into out[0..n); out must have room for n ints.
void mergeSort(int* nums, int n, int* out) {
// Base case: 0 or 1 element is already sorted — nothing to do.
if (n <= 1) {
memcpy(out, nums, (size_t)n * sizeof(int));
return;
}
// Divide: split down the middle and sort each half recursively.
int mid = n / 2;
int* left = malloc((size_t)mid * sizeof(int));
int* right = malloc((size_t)(n - mid) * sizeof(int));
mergeSort(nums, mid, left);
mergeSort(nums + mid, n - mid, right);
// Conquer: both halves are sorted, so merge them into out.
merge(left, mid, right, n - mid, out);
free(left);
free(right);
}
// merge combines two already-sorted arrays into out.
static void merge(int* a, int an, int* b, int bn, int* out) {
// Each input gets a read index; out gets a write index.
int i = 0, j = 0, k = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < an && j < bn) {
}
}#include <stdlib.h>
#include <string.h>
// Declared up front so mergeSort can call it before it is defined further down.
static void merge(int* a, int an, int* b, int bn, int* out);
// Sorts nums[0..n) into out[0..n); out must have room for n ints.
void mergeSort(int* nums, int n, int* out) {
// Base case: 0 or 1 element is already sorted — nothing to do.
if (n <= 1) {
memcpy(out, nums, (size_t)n * sizeof(int));
return;
}
// Divide: split down the middle and sort each half recursively.
int mid = n / 2;
int* left = malloc((size_t)mid * sizeof(int));
int* right = malloc((size_t)(n - mid) * sizeof(int));
mergeSort(nums, mid, left);
mergeSort(nums + mid, n - mid, right);
// Conquer: both halves are sorted, so merge them into out.
merge(left, mid, right, n - mid, out);
free(left);
free(right);
}
// merge combines two already-sorted arrays into out.
static void merge(int* a, int an, int* b, int bn, int* out) {
// Each input gets a read index; out gets a write index.
int i = 0, j = 0, k = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < an && j < bn) {
// Using <= (not <) keeps equal elements in their original order — stable.
}
}#include <stdlib.h>
#include <string.h>
// Declared up front so mergeSort can call it before it is defined further down.
static void merge(int* a, int an, int* b, int bn, int* out);
// Sorts nums[0..n) into out[0..n); out must have room for n ints.
void mergeSort(int* nums, int n, int* out) {
// Base case: 0 or 1 element is already sorted — nothing to do.
if (n <= 1) {
memcpy(out, nums, (size_t)n * sizeof(int));
return;
}
// Divide: split down the middle and sort each half recursively.
int mid = n / 2;
int* left = malloc((size_t)mid * sizeof(int));
int* right = malloc((size_t)(n - mid) * sizeof(int));
mergeSort(nums, mid, left);
mergeSort(nums + mid, n - mid, right);
// Conquer: both halves are sorted, so merge them into out.
merge(left, mid, right, n - mid, out);
free(left);
free(right);
}
// merge combines two already-sorted arrays into out.
static void merge(int* a, int an, int* b, int bn, int* out) {
// Each input gets a read index; out gets a write index.
int i = 0, j = 0, k = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < an && j < bn) {
// Using <= (not <) keeps equal elements in their original order — stable.
if (a[i] <= b[j]) {
out[k++] = a[i++];
} else {
out[k++] = b[j++];
}
}
}#include <stdlib.h>
#include <string.h>
// Declared up front so mergeSort can call it before it is defined further down.
static void merge(int* a, int an, int* b, int bn, int* out);
// Sorts nums[0..n) into out[0..n); out must have room for n ints.
void mergeSort(int* nums, int n, int* out) {
// Base case: 0 or 1 element is already sorted — nothing to do.
if (n <= 1) {
memcpy(out, nums, (size_t)n * sizeof(int));
return;
}
// Divide: split down the middle and sort each half recursively.
int mid = n / 2;
int* left = malloc((size_t)mid * sizeof(int));
int* right = malloc((size_t)(n - mid) * sizeof(int));
mergeSort(nums, mid, left);
mergeSort(nums + mid, n - mid, right);
// Conquer: both halves are sorted, so merge them into out.
merge(left, mid, right, n - mid, out);
free(left);
free(right);
}
// merge combines two already-sorted arrays into out.
static void merge(int* a, int an, int* b, int bn, int* out) {
// Each input gets a read index; out gets a write index.
int i = 0, j = 0, k = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < an && j < bn) {
// Using <= (not <) keeps equal elements in their original order — stable.
if (a[i] <= b[j]) {
out[k++] = a[i++];
} else {
out[k++] = b[j++];
}
}
// Exactly one side has leftovers (already sorted); copy them as-is.
}#include <stdlib.h>
#include <string.h>
// Declared up front so mergeSort can call it before it is defined further down.
static void merge(int* a, int an, int* b, int bn, int* out);
// Sorts nums[0..n) into out[0..n); out must have room for n ints.
void mergeSort(int* nums, int n, int* out) {
// Base case: 0 or 1 element is already sorted — nothing to do.
if (n <= 1) {
memcpy(out, nums, (size_t)n * sizeof(int));
return;
}
// Divide: split down the middle and sort each half recursively.
int mid = n / 2;
int* left = malloc((size_t)mid * sizeof(int));
int* right = malloc((size_t)(n - mid) * sizeof(int));
mergeSort(nums, mid, left);
mergeSort(nums + mid, n - mid, right);
// Conquer: both halves are sorted, so merge them into out.
merge(left, mid, right, n - mid, out);
free(left);
free(right);
}
// merge combines two already-sorted arrays into out.
static void merge(int* a, int an, int* b, int bn, int* out) {
// Each input gets a read index; out gets a write index.
int i = 0, j = 0, k = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < an && j < bn) {
// Using <= (not <) keeps equal elements in their original order — stable.
if (a[i] <= b[j]) {
out[k++] = a[i++];
} else {
out[k++] = b[j++];
}
}
// Exactly one side has leftovers (already sorted); copy them as-is.
while (i < an) {
out[k++] = a[i++];
}
while (j < bn) {
out[k++] = b[j++];
}
}#include <vector>
using namespace std;
// Declared up front so mergeSort can call it below. Named
// mergeSorted because <algorithm> already declares
// std::merge, which "using namespace std" brings into scope.
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b);
vector<int> mergeSort(const vector<int>& nums) {
}#include <vector>
using namespace std;
// Declared up front so mergeSort can call it below. Named
// mergeSorted because <algorithm> already declares
// std::merge, which "using namespace std" brings into scope.
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b);
vector<int> mergeSort(const vector<int>& nums) {
// Base case: a vector of length 0 or 1 is already sorted — nothing to do.
}#include <vector>
using namespace std;
// Declared up front so mergeSort can call it below. Named
// mergeSorted because <algorithm> already declares
// std::merge, which "using namespace std" brings into scope.
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b);
vector<int> mergeSort(const vector<int>& nums) {
// Base case: a vector of length 0 or 1 is already sorted — nothing to do.
if (nums.size() <= 1) {
return nums;
}
}#include <vector>
using namespace std;
// Declared up front so mergeSort can call it below. Named
// mergeSorted because <algorithm> already declares
// std::merge, which "using namespace std" brings into scope.
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b);
vector<int> mergeSort(const vector<int>& nums) {
// Base case: a vector of length 0 or 1 is already sorted — nothing to do.
if (nums.size() <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
}#include <vector>
using namespace std;
// Declared up front so mergeSort can call it below. Named
// mergeSorted because <algorithm> already declares
// std::merge, which "using namespace std" brings into scope.
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b);
vector<int> mergeSort(const vector<int>& nums) {
// Base case: a vector of length 0 or 1 is already sorted — nothing to do.
if (nums.size() <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = (int)nums.size() / 2;
vector<int> left = mergeSort(vector<int>(nums.begin(), nums.begin() + mid));
vector<int> right = mergeSort(vector<int>(nums.begin() + mid, nums.end()));
}#include <vector>
using namespace std;
// Declared up front so mergeSort can call it below. Named
// mergeSorted because <algorithm> already declares
// std::merge, which "using namespace std" brings into scope.
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b);
vector<int> mergeSort(const vector<int>& nums) {
// Base case: a vector of length 0 or 1 is already sorted — nothing to do.
if (nums.size() <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = (int)nums.size() / 2;
vector<int> left = mergeSort(vector<int>(nums.begin(), nums.begin() + mid));
vector<int> right = mergeSort(vector<int>(nums.begin() + mid, nums.end()));
// Conquer: both halves are sorted, so merge them into one sorted vector.
}#include <vector>
using namespace std;
// Declared up front so mergeSort can call it below. Named
// mergeSorted because <algorithm> already declares
// std::merge, which "using namespace std" brings into scope.
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b);
vector<int> mergeSort(const vector<int>& nums) {
// Base case: a vector of length 0 or 1 is already sorted — nothing to do.
if (nums.size() <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = (int)nums.size() / 2;
vector<int> left = mergeSort(vector<int>(nums.begin(), nums.begin() + mid));
vector<int> right = mergeSort(vector<int>(nums.begin() + mid, nums.end()));
// Conquer: both halves are sorted, so merge them into one sorted vector.
return mergeSorted(left, right);
}#include <vector>
using namespace std;
// Declared up front so mergeSort can call it below. Named
// mergeSorted because <algorithm> already declares
// std::merge, which "using namespace std" brings into scope.
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b);
vector<int> mergeSort(const vector<int>& nums) {
// Base case: a vector of length 0 or 1 is already sorted — nothing to do.
if (nums.size() <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = (int)nums.size() / 2;
vector<int> left = mergeSort(vector<int>(nums.begin(), nums.begin() + mid));
vector<int> right = mergeSort(vector<int>(nums.begin() + mid, nums.end()));
// Conquer: both halves are sorted, so merge them into one sorted vector.
return mergeSorted(left, right);
}
// mergeSorted combines two already-sorted vectors into one sorted vector.
// Reserve the exact capacity, and give each input its own read index.
#include <vector>
using namespace std;
// Declared up front so mergeSort can call it below. Named
// mergeSorted because <algorithm> already declares
// std::merge, which "using namespace std" brings into scope.
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b);
vector<int> mergeSort(const vector<int>& nums) {
// Base case: a vector of length 0 or 1 is already sorted — nothing to do.
if (nums.size() <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = (int)nums.size() / 2;
vector<int> left = mergeSort(vector<int>(nums.begin(), nums.begin() + mid));
vector<int> right = mergeSort(vector<int>(nums.begin() + mid, nums.end()));
// Conquer: both halves are sorted, so merge them into one sorted vector.
return mergeSorted(left, right);
}
// mergeSorted combines two already-sorted vectors into one sorted vector.
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b) {
// Reserve the exact capacity, and give each input its own read index.
vector<int> res;
res.reserve(a.size() + b.size());
size_t i = 0, j = 0;
}#include <vector>
using namespace std;
// Declared up front so mergeSort can call it below. Named
// mergeSorted because <algorithm> already declares
// std::merge, which "using namespace std" brings into scope.
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b);
vector<int> mergeSort(const vector<int>& nums) {
// Base case: a vector of length 0 or 1 is already sorted — nothing to do.
if (nums.size() <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = (int)nums.size() / 2;
vector<int> left = mergeSort(vector<int>(nums.begin(), nums.begin() + mid));
vector<int> right = mergeSort(vector<int>(nums.begin() + mid, nums.end()));
// Conquer: both halves are sorted, so merge them into one sorted vector.
return mergeSorted(left, right);
}
// mergeSorted combines two already-sorted vectors into one sorted vector.
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b) {
// Reserve the exact capacity, and give each input its own read index.
vector<int> res;
res.reserve(a.size() + b.size());
size_t i = 0, j = 0;
// While both still have elements, compare their fronts and take the smaller.
}#include <vector>
using namespace std;
// Declared up front so mergeSort can call it below. Named
// mergeSorted because <algorithm> already declares
// std::merge, which "using namespace std" brings into scope.
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b);
vector<int> mergeSort(const vector<int>& nums) {
// Base case: a vector of length 0 or 1 is already sorted — nothing to do.
if (nums.size() <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = (int)nums.size() / 2;
vector<int> left = mergeSort(vector<int>(nums.begin(), nums.begin() + mid));
vector<int> right = mergeSort(vector<int>(nums.begin() + mid, nums.end()));
// Conquer: both halves are sorted, so merge them into one sorted vector.
return mergeSorted(left, right);
}
// mergeSorted combines two already-sorted vectors into one sorted vector.
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b) {
// Reserve the exact capacity, and give each input its own read index.
vector<int> res;
res.reserve(a.size() + b.size());
size_t i = 0, j = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.size() && j < b.size()) {
}
}#include <vector>
using namespace std;
// Declared up front so mergeSort can call it below. Named
// mergeSorted because <algorithm> already declares
// std::merge, which "using namespace std" brings into scope.
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b);
vector<int> mergeSort(const vector<int>& nums) {
// Base case: a vector of length 0 or 1 is already sorted — nothing to do.
if (nums.size() <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = (int)nums.size() / 2;
vector<int> left = mergeSort(vector<int>(nums.begin(), nums.begin() + mid));
vector<int> right = mergeSort(vector<int>(nums.begin() + mid, nums.end()));
// Conquer: both halves are sorted, so merge them into one sorted vector.
return mergeSorted(left, right);
}
// mergeSorted combines two already-sorted vectors into one sorted vector.
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b) {
// Reserve the exact capacity, and give each input its own read index.
vector<int> res;
res.reserve(a.size() + b.size());
size_t i = 0, j = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.size() && j < b.size()) {
// Using <= (not <) keeps equal elements in their original order — stable.
}
}#include <vector>
using namespace std;
// Declared up front so mergeSort can call it below. Named
// mergeSorted because <algorithm> already declares
// std::merge, which "using namespace std" brings into scope.
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b);
vector<int> mergeSort(const vector<int>& nums) {
// Base case: a vector of length 0 or 1 is already sorted — nothing to do.
if (nums.size() <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = (int)nums.size() / 2;
vector<int> left = mergeSort(vector<int>(nums.begin(), nums.begin() + mid));
vector<int> right = mergeSort(vector<int>(nums.begin() + mid, nums.end()));
// Conquer: both halves are sorted, so merge them into one sorted vector.
return mergeSorted(left, right);
}
// mergeSorted combines two already-sorted vectors into one sorted vector.
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b) {
// Reserve the exact capacity, and give each input its own read index.
vector<int> res;
res.reserve(a.size() + b.size());
size_t i = 0, j = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.size() && j < b.size()) {
// Using <= (not <) keeps equal elements in their original order — stable.
if (a[i] <= b[j]) {
res.push_back(a[i]);
i++;
} else {
res.push_back(b[j]);
j++;
}
}
}#include <vector>
using namespace std;
// Declared up front so mergeSort can call it below. Named
// mergeSorted because <algorithm> already declares
// std::merge, which "using namespace std" brings into scope.
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b);
vector<int> mergeSort(const vector<int>& nums) {
// Base case: a vector of length 0 or 1 is already sorted — nothing to do.
if (nums.size() <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = (int)nums.size() / 2;
vector<int> left = mergeSort(vector<int>(nums.begin(), nums.begin() + mid));
vector<int> right = mergeSort(vector<int>(nums.begin() + mid, nums.end()));
// Conquer: both halves are sorted, so merge them into one sorted vector.
return mergeSorted(left, right);
}
// mergeSorted combines two already-sorted vectors into one sorted vector.
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b) {
// Reserve the exact capacity, and give each input its own read index.
vector<int> res;
res.reserve(a.size() + b.size());
size_t i = 0, j = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.size() && j < b.size()) {
// Using <= (not <) keeps equal elements in their original order — stable.
if (a[i] <= b[j]) {
res.push_back(a[i]);
i++;
} else {
res.push_back(b[j]);
j++;
}
}
// Exactly one side has leftovers (already sorted); append them as-is.
}#include <vector>
using namespace std;
// Declared up front so mergeSort can call it below. Named
// mergeSorted because <algorithm> already declares
// std::merge, which "using namespace std" brings into scope.
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b);
vector<int> mergeSort(const vector<int>& nums) {
// Base case: a vector of length 0 or 1 is already sorted — nothing to do.
if (nums.size() <= 1) {
return nums;
}
// Divide: split down the middle and sort each half recursively.
int mid = (int)nums.size() / 2;
vector<int> left = mergeSort(vector<int>(nums.begin(), nums.begin() + mid));
vector<int> right = mergeSort(vector<int>(nums.begin() + mid, nums.end()));
// Conquer: both halves are sorted, so merge them into one sorted vector.
return mergeSorted(left, right);
}
// mergeSorted combines two already-sorted vectors into one sorted vector.
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b) {
// Reserve the exact capacity, and give each input its own read index.
vector<int> res;
res.reserve(a.size() + b.size());
size_t i = 0, j = 0;
// While both still have elements, compare their fronts and take the smaller.
while (i < a.size() && j < b.size()) {
// Using <= (not <) keeps equal elements in their original order — stable.
if (a[i] <= b[j]) {
res.push_back(a[i]);
i++;
} else {
res.push_back(b[j]);
j++;
}
}
// Exactly one side has leftovers (already sorted); append them as-is.
res.insert(res.end(), a.begin() + i, a.end());
res.insert(res.end(), b.begin() + j, b.end());
return res;
}Tap the left half to go back, the right half to go forward.
Arrow keys or space to navigate · Esc to exit.