
## Introduction to Algorithms by CLRS version of Merge Sort

I like this version of more than the regular merge sort version because we can see much more clarity
in terms of recursion. Initially, the letters `p, q, r` might looks strange but they just denote p
as the 0th index, q as a mid-point index, r as the last index

## Main function's pseudocode

- For an input array A[p…r]
- Find the floor mid-point q as (p+q)/2
- mergesort(A, p, q)
- mergesort(A, q+1, r)
- merge(A, p, q, r)

## Merge function's pseudocode

In the below pseudocode, setting the B and C as infinity helps us avoid running through the last
remaining array for which we have to write 2 loops in the regular merge sort version. Inserting a
“Sentinel” value, in this case a value that will be larger than any real value in the array, at the
end of the array will make the check against it always fail. Also, sentinel value can be thought of
as a value that terminates the loop.

- create B and C as new arrays
- set i and j as 0
- copy A[p..q] to B and A[q+1..r] to C
- set B’s and C’s last item as Infinity
- for k = p to r:
  - if B[i] is less than C[j]
    - set A[k] as B[i] and increment i
  - else if B[i] is more than C[j]
    - set A[k] to C[j] and increment j

## Final Code

```js
var input = [1, 5, 5, 2, 9, 4, 8, 7, 4, 5, 1, 0, 8, 2, 1, -1, -3]

function mergeSort(A, p, r) {
  if (p >= r) return

  var q = Math.floor((p + r) / 2)
  mergeSort(A, p, q)
  mergeSort(A, q + 1, r)
  merge(A, p, q, r)
}

function merge(A, p, q, r) {
  var B = [],
    C = []
  var i = 0,
    j = 0

  for (var m = p; m <= q; m++) {
    B.push(A[m])
  }

  for (var m = q + 1; m <= r; m++) {
    C.push(A[m])
  }

  B.push(Infinity)
  C.push(Infinity)

  for (var k = p; k <= r; k++) {
    if (B[i] <= C[j]) {
      A[k] = B[i]
      i++
    } else if (B[i] > C[j]) {
      A[k] = C[j]
      j++
    }
  }
}

mergeSort(input, 0, input.length - 1)
console.log(input)
```


CLRS Merge Sort in JavaScript


## Overview

- It’s a standard recursive algorithm similar to binary search.
- The array is split until the pairs or individual item exist . The pairs are sorted.
- A merge routine then merges the 2 sorted arrays and this repeats until all the parts are merged.

## Merge Routine

The merge routine is as following for 2 sorted arrays:
[MIT Ref](https://www.youtube.com/watch?v=bOk35XmHPKs)

| Left Sorted Array | Right Sorted Array |
| ----------------- | ------------------ |
| 20                | 12                 |
| 13                | 11                 |
| 7                 | 9                  |
| 2                 | 1                  |

Steps to merge the left and right array:

- use 3 pointers for left half, right half and the resulting sorted array.
  [YT Ref](https://www.youtube.com/watch?v=bOk35XmHPKs)
- compare 1(i) & 2(j), strike off 1, push 1 at an index(k) in new array and move the pointer to 9
- compare 9 & 7, strike off 7, push 7 at an index(k) new array and move the pointer to 13
- repeat

## Code for Merge

- sorting will an easier operation as we are going to swap the A[0] and A[1] of the split array.

```javascript
function merge(input, leftHalf, rightHalf) {
  var leftSize = leftHalf.length
  var rightSize = rightHalf.length
  var i = 0,
    j = 0,
    k = 0

  while (i < leftSize && j < rightSize) {
    if (leftHalf[i] <= rightHalf[j]) {
      input[k] = leftHalf[i]
      i++
    } else {
      input[k] = rightHalf[j]
      j++
    }
    k++
  }

  while (i < leftSize) {
    input[k] = leftHalf[i]
    i++
    k++
  }

  while (j < rightSize) {
    input[k] = rightHalf[j]
    j++
    k++
  }
}
```

## Code for Split and Sort Recursively

```js
function mergeSort(input) {
  var leftHalf = []
  var rightHalf = []
  var remains = input.length % 2
  var middle = (input.length + remains) / 2

  if (input.length < 2) {
    return input
  }

  for (var i = 0; i < middle; i++) {
    leftHalf[i] = input[i]
  }

  for (var i = middle; i < input.length; i++) {
    rightHalf[i - middle] = input[i]
  }

  mergeSort(leftHalf)
  mergeSort(rightHalf)

  merge(input, leftHalf, rightHalf)
}
```

## Final Complete Code

```js
var input = [2, 74, 12, 9, 1, 1, 1, 0, 9, 6, 5, 6, 6, 5]

function merge(input, leftHalf, rightHalf) {
  var leftSize = leftHalf.length
  var rightSize = rightHalf.length
  var i = 0,
    j = 0,
    k = 0

  while (i < leftSize && j < rightSize) {
    if (leftHalf[i] <= rightHalf[j]) {
      input[k] = leftHalf[i]
      i++
    } else {
      input[k] = rightHalf[j]
      j++
    }
    k++
  }

  while (i < leftSize) {
    input[k] = leftHalf[i]
    i++
    k++
  }

  while (j < rightSize) {
    input[k] = rightHalf[j]
    j++
    k++
  }
}

function mergeSort(input) {
  var leftHalf = []
  var rightHalf = []
  var remains = input.length % 2
  var middle = (input.length + remains) / 2

  if (input.length < 2) {
    return input
  }

  for (var i = 0; i < middle; i++) {
    leftHalf[i] = input[i]
  }

  for (var i = middle; i < input.length; i++) {
    rightHalf[i - middle] = input[i]
  }

  mergeSort(leftHalf)
  mergeSort(rightHalf)

  merge(input, leftHalf, rightHalf)
}

mergeSort(input)
console.log(input)
```


Merge Sort in JavaScript


## Overview

Its similar to Merge Sort where we apply divide and conquer approach but unlike Merge sort there is
no need to combine because Quicksort sorts in-place.

## Divide

**Pivot** can be selected by choosing :

- A right most item in the list.
- A randomly selected value is also taken as pivot, the random item is then swapped with the last
  item in the list.
- A set of three random values are picked, the median value among the 3 is swapped with the last
  item in the list.
- Items that are less than pivot are collected in left and right if otherwise.
- The above evaluation will not guarantee sorted items in the left or right.

## Conquer

The left and right chunk are repeated applied with the same evaluation.

## Combine

No combine needed unlike merge sort, because the sorting happens in-place.

## Main Method Pseudocode

- function that takes: A (input), p(starting index), r(pivot's index)
  - if p ≥ r then do nothing
  - get q(dividing line between the left and right chunk) by partitioning
  - invoke the main method with the left chunk with (A, p, q-1) as parameters
  - invoke the main method with the right chunk with (A, q+1, r) as parameters

## Partition Pseudocode

- function that takes: A(input), p(starting index), r(pivot's index)
  - set q as p
  - loop through the input
    - check if the current value of the input is less than the pivot
    - then swap the current value with the q
  - after the loop, swap the r with the q ( this put the pivot in between the left and right chunks)

## Code

```js
var A = [5, 4, 3, 1, 4, 53, 1, 4, 6, 3, 7, 3, 11, 2, 1, 5, 7, 3]

function quicksort(A, p, r) {
  if (p >= r) return

  var q = partition(A, p, r)
  quicksort(A, p, q - 1)
  quicksort(A, q + 1, r)
}

function partition(A, p, r) {
  var q = p

  for (var u = p; u <= r - 1; u++) {
    if (A[u] <= A[r]) {
      ;[A[q], A[u]] = [A[u], A[q]]
      q++
    }
  }
  ;[A[q], A[r]] = [A[r], A[q]]
  return q
}

quicksort(A, 0, A.length - 1)
console.log(A)
```


algorithms

algorithms

3 Tutorials

CLRS Merge Sort in JavaScript

Merge Sort in JavaScript

Quicksort in JavaScript