onenoughtone

Merge Sort Pattern

What is the Merge Sort Pattern?

The Merge Sort pattern is a divide and conquer approach that divides a problem into smaller subproblems, solves them independently, and then merges the results.

It's characterized by its efficient merging step, which combines the solutions of subproblems to form the solution to the original problem.

Key Steps

Divide: Split the input into smaller, manageable pieces
Conquer: Solve each piece recursively
Combine: Merge the solved pieces to form the solution to the original problem

Merge Sort Implementation

Here's an implementation of the classic merge sort algorithm:

Time and Space Complexity

Time Complexity:

O(n log n) for all cases (best, average, worst), where n is the number of elements in the array.

Space Complexity:

O(n) for the auxiliary arrays used during the merge step.

Application: Counting Inversions

The merge sort pattern can be adapted to count inversions in an array (pairs of elements that are out of order):

Previous Next

Pattern 1: Merge Sort

Learn the merge-based pattern of divide and conquer through the classic merge sort algorithm and its applications.

What is the Merge Sort Pattern?

The Merge Sort pattern is a divide and conquer approach that divides a problem into smaller subproblems, solves them independently, and then merges the results.

It's characterized by its efficient merging step, which combines the solutions of subproblems to form the solution to the original problem.

Example:

Input: [38, 27, 43, 3, 9, 82, 10]

Divide: [38, 27, 43, 3] and [9, 82, 10]

Conquer: Sort each half recursively

Combine: Merge [3, 27, 38, 43] and [9, 10, 82] to get [3, 9, 10, 27, 38, 43, 82]

Key Characteristics

Stable Sorting

Preserves the relative order of equal elements, making it suitable for multi-level sorting.

Predictable Performance

O(n log n) time complexity in all cases, regardless of the input distribution.

Not In-Place

Requires additional O(n) space for the merge step, making it less memory-efficient than some other sorting algorithms.

Parallelizable

The divide and conquer nature makes it suitable for parallel processing, as subproblems can be solved independently.

The Three Steps of Merge Sort

1Divide

Split the array into two halves. If the array has an odd number of elements, one half will have one more element than the other.

2Conquer

Recursively sort both halves. If the array has only one element, it's already sorted (base case).

3Combine

Merge the two sorted halves to produce a single sorted array. This is done by comparing elements from both halves and adding the smaller one to the result.

Merge Sort Implementation

Here's an implementation of the classic merge sort algorithm:

mergeSort.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function mergeSort(arr) {
  // Base case: arrays with 0 or 1 element are already sorted
  if (arr.length <= 1) {
    return arr;
  }
 
  // Divide: Split the array into two halves
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
 
  // Conquer: Recursively sort both halves
  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);
 
  // Combine: Merge the sorted halves
  return merge(sortedLeft, sortedRight);
}
 
function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;
 
  // Compare elements from both arrays and add the smaller one to the result
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }
 
  // Add remaining elements
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

Key Insight: The merge function is the heart of the algorithm. It efficiently combines two sorted arrays into a single sorted array by comparing elements from both arrays and adding the smaller one to the result.

Time and Space Complexity

Time Complexity

O(n log n) for all cases (best, average, worst), where n is the number of elements in the array.

Explanation: The array is divided log n times (until each subarray has 1 element), and each level of division requires O(n) work to merge the subarrays.

Space Complexity

O(n) for the auxiliary arrays used during the merge step.

Explanation: The merge function creates temporary arrays to store the merged result, requiring O(n) extra space. The recursion stack also uses O(log n) space, but the O(n) term dominates.

Advantages and Disadvantages

Advantages

Stable sorting algorithm (preserves order of equal elements)
Guaranteed O(n log n) performance regardless of input
Well-suited for linked lists (requires only sequential access)
Parallelizable due to independent subproblems

Disadvantages

Requires O(n) extra space (not in-place)
Slower than quick sort for small arrays due to overhead
Not cache-efficient due to non-local memory references
More complex implementation than some other sorting algorithms

Application: Counting Inversions

The merge sort pattern can be adapted to count inversions in an array. An inversion is a pair of elements that are out of order (i.e., a[i] > a[j] where i < j).

countInversions.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
function countInversions(arr) {
  // Base case: arrays with 0 or 1 element have 0 inversions
  if (arr.length <= 1) {
    return { sortedArray: arr, inversions: 0 };
  }
 
  // Divide: Split the array into two halves
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
 
  // Conquer: Recursively count inversions in both halves
  const leftResult = countInversions(left);
  const rightResult = countInversions(right);
 
  // Combine: Merge the sorted halves and count split inversions
  const mergeResult = mergeAndCount(leftResult.sortedArray, rightResult.sortedArray);
 
  // Total inversions = inversions in left + inversions in right + split inversions
  return {
    sortedArray: mergeResult.sortedArray,
    inversions: leftResult.inversions + rightResult.inversions + mergeResult.inversions
  };
}
 
function mergeAndCount(left, right) {
  let sortedArray = [];
  let inversions = 0;
  let leftIndex = 0;
  let rightIndex = 0;
 
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      sortedArray.push(left[leftIndex]);
      leftIndex++;
    } else {
      // If left[leftIndex] > right[rightIndex], it forms inversions with all
      // remaining elements in the left array
      sortedArray.push(right[rightIndex]);
      inversions += (left.length - leftIndex);
      rightIndex++;
    }
  }
 
  // Add remaining elements
  sortedArray = sortedArray.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
 
  return { sortedArray, inversions };
}

How it works: When merging two sorted arrays, if an element from the right array is smaller than an element from the left array, it forms inversions with all remaining elements in the left array. By counting these occurrences during the merge step, we can count all inversions in the array in O(n log n) time.

Previous: Divide and Conquer Patterns Next: Quick Sort Pattern

Intro Visualize Patterns Practice

onenoughtone

Back to Home

onenoughtone

Back to Home

Merge Sort Pattern

What is the Merge Sort Pattern?

The Merge Sort pattern is a divide and conquer approach that divides a problem into smaller subproblems, solves them independently, and then merges the results.

It's characterized by its efficient merging step, which combines the solutions of subproblems to form the solution to the original problem.

Key Steps

Divide: Split the input into smaller, manageable pieces
Conquer: Solve each piece recursively
Combine: Merge the solved pieces to form the solution to the original problem

Merge Sort Implementation

Here's an implementation of the classic merge sort algorithm:

Time and Space Complexity

Time Complexity:

O(n log n) for all cases (best, average, worst), where n is the number of elements in the array.

Space Complexity:

O(n) for the auxiliary arrays used during the merge step.

Application: Counting Inversions

The merge sort pattern can be adapted to count inversions in an array (pairs of elements that are out of order):

Previous Next

Pattern 1: Merge Sort

Learn the merge-based pattern of divide and conquer through the classic merge sort algorithm and its applications.

What is the Merge Sort Pattern?

The Merge Sort pattern is a divide and conquer approach that divides a problem into smaller subproblems, solves them independently, and then merges the results.

It's characterized by its efficient merging step, which combines the solutions of subproblems to form the solution to the original problem.

Example:

Input: [38, 27, 43, 3, 9, 82, 10]

Divide: [38, 27, 43, 3] and [9, 82, 10]

Conquer: Sort each half recursively

Combine: Merge [3, 27, 38, 43] and [9, 10, 82] to get [3, 9, 10, 27, 38, 43, 82]

Key Characteristics

Stable Sorting

Preserves the relative order of equal elements, making it suitable for multi-level sorting.

Predictable Performance

O(n log n) time complexity in all cases, regardless of the input distribution.

Not In-Place

Requires additional O(n) space for the merge step, making it less memory-efficient than some other sorting algorithms.

Parallelizable

The divide and conquer nature makes it suitable for parallel processing, as subproblems can be solved independently.

The Three Steps of Merge Sort

1Divide

Split the array into two halves. If the array has an odd number of elements, one half will have one more element than the other.

2Conquer

Recursively sort both halves. If the array has only one element, it's already sorted (base case).

3Combine

Merge the two sorted halves to produce a single sorted array. This is done by comparing elements from both halves and adding the smaller one to the result.

Merge Sort Implementation

Here's an implementation of the classic merge sort algorithm:

mergeSort.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function mergeSort(arr) {
  // Base case: arrays with 0 or 1 element are already sorted
  if (arr.length <= 1) {
    return arr;
  }
 
  // Divide: Split the array into two halves
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
 
  // Conquer: Recursively sort both halves
  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);
 
  // Combine: Merge the sorted halves
  return merge(sortedLeft, sortedRight);
}
 
function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;
 
  // Compare elements from both arrays and add the smaller one to the result
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }
 
  // Add remaining elements
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

Time and Space Complexity

Time Complexity

O(n log n) for all cases (best, average, worst), where n is the number of elements in the array.

Explanation: The array is divided log n times (until each subarray has 1 element), and each level of division requires O(n) work to merge the subarrays.

Space Complexity

O(n) for the auxiliary arrays used during the merge step.

Explanation: The merge function creates temporary arrays to store the merged result, requiring O(n) extra space. The recursion stack also uses O(log n) space, but the O(n) term dominates.

Advantages and Disadvantages

Advantages

Stable sorting algorithm (preserves order of equal elements)
Guaranteed O(n log n) performance regardless of input
Well-suited for linked lists (requires only sequential access)
Parallelizable due to independent subproblems

Disadvantages

Requires O(n) extra space (not in-place)
Slower than quick sort for small arrays due to overhead
Not cache-efficient due to non-local memory references
More complex implementation than some other sorting algorithms

Application: Counting Inversions

The merge sort pattern can be adapted to count inversions in an array. An inversion is a pair of elements that are out of order (i.e., a[i] > a[j] where i < j).

countInversions.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
function countInversions(arr) {
  // Base case: arrays with 0 or 1 element have 0 inversions
  if (arr.length <= 1) {
    return { sortedArray: arr, inversions: 0 };
  }
 
  // Divide: Split the array into two halves
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
 
  // Conquer: Recursively count inversions in both halves
  const leftResult = countInversions(left);
  const rightResult = countInversions(right);
 
  // Combine: Merge the sorted halves and count split inversions
  const mergeResult = mergeAndCount(leftResult.sortedArray, rightResult.sortedArray);
 
  // Total inversions = inversions in left + inversions in right + split inversions
  return {
    sortedArray: mergeResult.sortedArray,
    inversions: leftResult.inversions + rightResult.inversions + mergeResult.inversions
  };
}
 
function mergeAndCount(left, right) {
  let sortedArray = [];
  let inversions = 0;
  let leftIndex = 0;
  let rightIndex = 0;
 
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      sortedArray.push(left[leftIndex]);
      leftIndex++;
    } else {
      // If left[leftIndex] > right[rightIndex], it forms inversions with all
      // remaining elements in the left array
      sortedArray.push(right[rightIndex]);
      inversions += (left.length - leftIndex);
      rightIndex++;
    }
  }
 
  // Add remaining elements
  sortedArray = sortedArray.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
 
  return { sortedArray, inversions };
}

Previous: Divide and Conquer Patterns Next: Quick Sort Pattern