Merge Two Sorted Arrays Without Extra Space in DSA Javascript

Mental Model

We combine two sorted lists into one sorted order without using extra space by cleverly swapping and sorting in place.

Analogy: Imagine two sorted stacks of books on a table side by side. Instead of moving books to a new shelf, you swap books between stacks to keep both stacks sorted without extra space.

Array1: [1, 5, 9, 10, 15, 20]
Array2: [2, 3, 8, 13]

Dry Run Walkthrough

Input: Array1: [1, 5, 9, 10, 15, 20], Array2: [2, 3, 8, 13]

Goal: Merge both arrays so that all elements are sorted across both arrays without using extra space

Step 1: Compare last element of Array1 (20) with first element of Array2 (2), swap because 20 > 2

Array1: [1, 5, 9, 10, 15, 2]
Array2: [20, 3, 8, 13]

Why: We want smaller elements in Array1 and larger in Array2 to keep arrays sorted after sorting

Step 2: Sort Array1 and Array2 individually after swap

Array1: [1, 2, 5, 9, 10, 15]
Array2: [3, 8, 13, 20]

Why: Sorting restores order after swapping elements

Step 3: Compare last element of Array1 (15) with first element of Array2 (3), swap because 15 > 3

Array1: [1, 2, 5, 9, 10, 3]
Array2: [15, 8, 13, 20]

Why: Continue swapping to ensure smaller elements are in Array1

Step 4: Sort Array1 and Array2 again

Array1: [1, 2, 3, 5, 9, 10]
Array2: [8, 13, 15, 20]

Why: Restore sorted order after swap

Step 5: Compare last element of Array1 (10) with first element of Array2 (8), swap because 10 > 8

Array1: [1, 2, 3, 5, 8, 10]
Array2: [9, 13, 15, 20]

Why: Final swap to ensure arrays are sorted across both

Step 6: Sort Array1 and Array2 one last time

Array1: [1, 2, 3, 5, 8, 9]
Array2: [10, 13, 15, 20]

Why: Final sorted arrays without extra space

Result:

Array1: [1, 2, 3, 5, 8, 9]
Array2: [10, 13, 15, 20]

Annotated Code

DSA Javascript

class MergeSortedArrays {
  static merge(arr1, arr2) {
    let n = arr1.length;
    let m = arr2.length;
    for (let i = n - 1; i >= 0; i--) {
      if (arr1[i] > arr2[0]) {
        // Swap if element in arr1 is greater than first element in arr2
        let temp = arr1[i];
        arr1[i] = arr2[0];
        arr2[0] = temp;

        // After swap, insert arr2[0] into correct position to keep arr2 sorted
        let first = arr2[0];
        let k;
        for (k = 1; k < m && arr2[k] < first; k++) {
          arr2[k - 1] = arr2[k];
        }
        arr2[k - 1] = first;
      }
    }
  }
}

// Driver code
const arr1 = [1, 5, 9, 10, 15, 20];
const arr2 = [2, 3, 8, 13];
MergeSortedArrays.merge(arr1, arr2);
console.log('Array1:', arr1.join(', '));
console.log('Array2:', arr2.join(', '));

for (let i = n - 1; i >= 0; i--) {

iterate backward through arr1 to compare larger elements

if (arr1[i] > arr2[0]) {

check if current arr1 element is bigger than smallest arr2 element

let temp = arr1[i]; arr1[i] = arr2[0]; arr2[0] = temp;

swap elements to move smaller to arr1 and larger to arr2

let first = arr2[0]; let k; for (k = 1; k < m && arr2[k] < first; k++) { arr2[k - 1] = arr2[k]; } arr2[k - 1] = first;

insert swapped element into correct position in arr2 to keep it sorted

Output

Array1: 1, 2, 3, 5, 8, 9

Array2: 10, 13, 15, 20

Complexity Analysis

Time: O(n*m) because for each element in arr1 we may shift elements in arr2 to keep it sorted

Space: O(1) because no extra arrays or data structures are used, only swaps and shifts in place

vs Alternative: Naive approach uses extra space to merge both arrays and then sort, costing O(n+m) space and O((n+m) log(n+m)) time, which is more space and time expensive

Edge Cases

One or both arrays empty

No swaps needed, arrays remain as is

DSA Javascript

for (let i = n - 1; i >= 0; i--) {

All elements in arr1 smaller than arr2

No swaps occur, arrays remain sorted

DSA Javascript

if (arr1[i] > arr2[0]) {

All elements in arr1 larger than arr2

Multiple swaps and shifts happen to reorder arrays correctly

DSA Javascript

let first = arr2[0]; let k; for (k = 1; k < m && arr2[k] < first; k++) { arr2[k - 1] = arr2[k]; } arr2[k - 1] = first;

When to Use This Pattern

When you need to merge two sorted arrays without extra space, look for in-place swapping and insertion to maintain order without extra memory.

Common Mistakes

Mistake: Trying to merge by appending and sorting which uses extra space
Fix: Use swapping and insertion in place to avoid extra space

Mistake: Not sorting arr2 after swapping, breaking its sorted order
Fix: After swapping, shift elements in arr2 to keep it sorted

Summary

Merges two sorted arrays into sorted order without using extra space by swapping and inserting elements in place.

Use when you must merge sorted arrays but cannot allocate extra memory.

The key insight is to swap larger elements from the first array with smaller elements from the second, then fix the second array's order by insertion.

Practice

1. What is the main goal when merging two sorted arrays without extra space?

easy

A. Sort each array separately without merging

B. Create a new array to hold all elements from both arrays

C. Copy elements from one array to another without sorting

D. Combine both arrays into one sorted array without using extra memory

Solution

1. Step 1: Understand the problem requirement

   The problem asks to merge two sorted arrays into a single sorted sequence without using extra space, meaning no additional arrays or large memory allocations.

2. Step 2: Identify the approach

   We must rearrange elements within the given arrays themselves to maintain sorted order combined.

3. Final Answer:

   Combine both arrays into one sorted array without using extra memory -> Option D

4. Quick Check:

   Merge without extra space = Combine in-place [OK]

Hint: Think in-place rearrangement, not new arrays [OK]

Common Mistakes:

• Assuming extra arrays are allowed
• Sorting arrays separately without merging
• Copying elements without sorting

2. Which of the following JavaScript syntax snippets correctly swaps two elements a[i] and b[j] without using a temporary variable?

easy

A. [a[i], b[j]] = [b[j], a[i]];

B. temp = a[i]; a[i] = b[j]; b[j] = temp;

C. a[i] = b[j]; b[j] = a[i];

D. a[i], b[j] = b[j], a[i];

Solution

1. Step 1: Identify correct swap syntax in JavaScript

   Using destructuring assignment, [a[i], b[j]] = [b[j], a[i]]; swaps values without a temporary variable.

2. Step 2: Check other options

   temp = a[i]; a[i] = b[j]; b[j] = temp; uses a temporary variable, C incorrectly assigns twice, D is invalid syntax.

3. Final Answer:

   [a[i], b[j]] = [b[j], a[i]]; -> Option A

4. Quick Check:

   Destructuring swap = [a[i], b[j]] = [b[j], a[i]]; [OK]

Hint: Use destructuring assignment for swap without temp [OK]

Common Mistakes:

• Using invalid syntax like option D
• Forgetting to use a temporary variable if not destructuring
• Assigning values incorrectly causing data loss

3. What will be the content of arrays a and b after running this code?

let a = [1, 5, 9, 10];
let b = [2, 3, 8, 13];

for (let i = 0; i < a.length; i++) {
  if (a[i] > b[0]) {
    [a[i], b[0]] = [b[0], a[i]];
    b.sort((x, y) => x - y);
  }
}

medium

A. a = [1, 2, 3, 5], b = [8, 9, 10, 13]

B. a = [1, 3, 5, 8], b = [2, 9, 10, 13]

C. a = [1, 2, 5, 8], b = [3, 9, 10, 13]

D. a = [1, 2, 3, 8], b = [5, 9, 10, 13]

Solution

1. Step 1: Trace the loop and swaps

   i=0: a[0]=1 <= b[0]=2 no swap
   i=1: a[1]=5 > b[0]=2 swap -> a[1]=2, b[0]=5; b sorted: [3,5,8,13]
   i=2: a[2]=9 > b[0]=3 swap -> a[2]=3, b[0]=9; b sorted: [5,8,9,13]
   i=3: a[3]=10 > b[0]=5 swap -> a[3]=5, b[0]=10; b sorted: [8,9,10,13]

2. Step 2: Final arrays after loop

   a = [1, 2, 3, 5]
   b = [8, 9, 10, 13]

3. Final Answer:

   a = [1, 2, 3, 5], b = [8, 9, 10, 13] -> Option A

4. Quick Check:

   Swapped and sorted b each time = a = [1, 2, 3, 5], b = [8, 9, 10, 13] [OK]

Hint: Swap if a[i] > b[0], then sort b [OK]

Common Mistakes:

• Not sorting array b after swap
• Swapping incorrectly causing wrong order
• Assuming arrays merge into one

4. Identify the error in this code snippet intended to merge two sorted arrays without extra space:

let a = [1, 4, 7];
let b = [2, 5, 6];

for (let i = 0; i < a.length; i++) {
  if (a[i] > b[0]) {
    let temp = a[i];
    a[i] = b[0];
    b[0] = temp;
  }
  b.sort();
}

medium

A. The if condition should be a[i] < b[0] instead of a[i] > b[0]

B. The sort() method is called without a compare function, causing incorrect sorting

C. Loop should run over array b length instead of a length

D. Swapping elements uses a temporary variable incorrectly

Solution

1. Step 1: Check the sorting method used

   The code uses b.sort() without a compare function, which sorts elements as strings, not numbers, causing wrong order.

2. Step 2: Correct sorting approach

   Use b.sort((x, y) => x - y) to sort numbers correctly.

3. Final Answer:

   The sort() method is called without a compare function, causing incorrect sorting -> Option B

4. Quick Check:

   sort() without compare = wrong numeric order [OK]

Hint: Always provide compare function for numeric sort [OK]

Common Mistakes:

• Using default sort() for numbers
• Swapping incorrectly without temp variable
• Wrong loop range

5. Given two sorted arrays a = [1, 3, 5, 7] and b = [0, 2, 6, 8, 9], how can you merge them without extra space so that after merging, a contains the first 4 smallest elements and b contains the remaining elements sorted? Which approach is best?

hard

A. Swap elements only if a[i] > b[j] without sorting b after swaps

B. Concatenate arrays and sort the combined array

C. Use a gap method to compare and swap elements between arrays until fully sorted

D. Copy all elements to a new array and then split back

Solution

1. Step 1: Understand the gap method

   The gap method compares elements at a certain gap distance in both arrays and swaps if needed, reducing the gap until 1, ensuring sorted order without extra space.

2. Step 2: Why other options fail

   Concatenate arrays and sort the combined array and D use extra space, violating constraints. Swap elements only if a[i] > b[j] without sorting b after swaps misses sorting after swaps, causing incorrect order.

3. Final Answer:

   Use a gap method to compare and swap elements between arrays until fully sorted -> Option C

4. Quick Check:

   Gap method = in-place merge without extra space [OK]

Hint: Use gap method to merge in-place efficiently [OK]

Common Mistakes:

• Using extra arrays violating constraints
• Not sorting after swaps causing disorder
• Assuming simple swaps suffice without gap reduction