
## 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)
```


Quicksort 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


https://youtu.be/ht9jxw8G0AE

Implicit binding applies when we use a function and invoke it as a method of an object. In that
case, the `this` keyword points to the object on which the method was invoked. In the following
examples you will notice that the invocation of `getName` was done using the object `person` and
thats what made the `this` keyword point to the `person` object.

```js
var person = {
  firstName: 'meher',
  getName: function () {
    console.log(this.firstName)
  },
}

person.getName() // outputs meher
```

## Function Outside the Method

Also, it does not matter whether the function was defined within the object or not. Look at the
below example, the function's definition location doesn't matter at all. But because the function
again invoked using the `person` object, the `this` keyword understand the context and points the to
the `person` object.

```js
function getName() {
  console.log(this.firstName)
}

var person = {
  firstName: 'meher',
  getName,
}

person.getName() // outputs meher
```

Now, you can notice that because function location doesn't matter, we can use this property to our
advantage and create a reusable function(s) that can be run on different objects and return
different result. Imagine, if we had `employee` object somewhere in the codebase and a `person`
object. Both object can reuse the `firstName` function.

## When Implicit Binding Fails

If you store the function reference in a variable and then invoke the function later. The implicit
binding is lost.

```js
var person = {
  firstName: 'meher',
  getName: function () {
    console.log(this.firstName)
  },
}

var fn = person.getName

fn() // looks up globally?
```

## Callbacks

In the case of the callbacks, the general rule these days is that whatever is on the left side,
which doesn't work . See why:

```js
function getName() {
  console.log(this.firstName)
}

var person = {
  firstName: 'meher',

  getName,
}

function displayFirstName(cb) {
  cb()
}

displayFirstName(person.getName)
```

Even when implicit-lost context is passed, the global issue is still raised.

```js
function getName() {
  console.log(this.firstName)
}

var person = {
  firstName: 'meher',
  getName,
}

setTimeout(person.getName, 1000)

// An implementation similar to this could be found in a library or native API:

function setTimeout(fn, delay) {
  fn()
}
```
