
## Introduction to Algorithms by CLRS version of Merge Sort 
I like this version of more than the previous 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 previous version. Inserting a “Sentinal” 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. 
- 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


## NextJS

For generating static site for performance. However, one thing I noticed really late in the development was that NextJS doesn't generate images of various sizes at build time. Making NextJS not a true static site generator.

## Bulma

Bulma is a vanilla CSS library, no JS based components. I needed something timeless for styling because I didn't want to use a component library that tightly binds style with logic. Because web is so evolving I didn’t to invest any time maintaining stylesheet, upgrading them and all the nuances that come with a library.

I knew I wanted something like sass based that supports nesting of classes and handles name-spacing. Luckily NextJS supports css modules out of the box to handle this. So now I just plain vanilla CSS using utilities from Bulma for grids, basic layout classes etc and NextJS takes care of the rest.

Now, by having NextJS CSS modules I do have added a layer of processing over my vanilla CSS. But even if I pull out css modules out of my system, I would just have to add a wrapping classname in my CSS because all my CSS is nested in a SASS like format.

## MDX

I am using Markdown X to write the contents of the post. Markdown was sufficient but I needed to rearrange the HTML structure that was generated from the markdown to be intercepted and rearranged in a different order or configuration. MDX does that by giving you a hook before it renders the document. My use case was creating a table of content for my post and I needed to have an anchor tag within the heading tag.

```js
## Heading -> <h2>Heading</h2> // Markdown
## Heading -> <h2><a href="intro">Heading</a></h2> // MDX
```

## Vercel

The deployment is handled by Vercel. It deploys on every push to the master and also takes care of the image generation which I highlighted earlier.


Libraries Aerosailor.com Uses


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


Quicksort in JavaScript


## Basic Rule

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()
}
```


Implicit Binding - THIS Keyword — Part-3


It’s the most common way to invoke a function. You already know it and have seen it a million times. It looks like this:

```js
function name() {
  console.log(this)
}

name()
```

Now, when you load such a code in your browser window through the dev console or an HTML document. The function `name` gets added to the global object, and in the case of a browser (the other being the Node environment), the global object is your window object.

The `window` object contains a number of functions, namespaces, objects, and constructors, and these are available globally across your codebase. And so when we ask JS about `this` within a function like this, what we get back is `window` object:

```js

Window {

    alert: ƒ alert()

    atob: ƒ atob()

    blur: ƒ blur()

    btoa: ƒ btoa()

    caches: CacheStorage {}

    cancelAnimationFrame: ƒ cancelAnimationFrame()

    cancelIdleCallback: ƒ cancelIdleCallback()

    captureEvents: ƒ captureEvents()

    chrome: {loadTimes: ƒ, csi: ƒ}

    clearInterval: ƒ clearInterval()

    clearTimeout: ƒ clearTimeout()

    ...

}

```

## But Why?

When an identifier, in our case, the function name, is added to the global object.

And when we are invoking the name` function, what JavaScript is actually doing behind the scenes is:

```js
window.name()
```

And it should be clear why this keyword is pointing to the window object because our `call-site` clearly shows that name should be invoked from the perspective of the window. And that's why `this` in a function in global scope points to the `window` object.

## Strict Mode

In strict mode, it's quite simple. You will get back `undefined`, which is an appropriate response and avoids all the confusion.

```js
"use strict"

function name() {
  console.log(this) //outputs undefined
}

name()
```

Even this, too...

```js
function name() {
  "use strict"

  console.log(this) //outputs undefined
}

name()
```

So that's one way the value of `this` keyword can have a different value. Now, let's look at the [next part]('/javascript/implicit-binding-this-keyword-part-3) which is [**Implicit Binding**]('/javascript/implicit-binding-this-keyword-part-3')


Default Binding - THIS Keyword — Part-2


In this tutorial, we will look at `this` keyword and break it down into five parts so that each part is bite-sized and easy to comprehend. By the end of this series, you will have a super solid intuitive mental model that will stay with you for the longest time.

## Background

The JavaScript language is quite inspired by the language Scheme. Scheme is the language that has inspired functional programming languages like Haskell and Closure.

But in later stages, the makers of JavaScript noticed a rise in the popularity of Java and decided to make JavaScript look like Java for easier adoption. And that choice brought many features from the object-oriented world into JS. And we know that a functional programming language doesn't have `this` keyword, but object-oriented programming does.

Even though JS decided to mimic the look and feel of Java, from within, JS is very much like Scheme. It does not implement a true object-oriented system, but JS achieves inhertiance by leveraging the prototype model. Although you might say that ES6 has classes, and it is nothing but syntactic sugar over the prototype system.

> ES6 classes are just a syntactic sugar over the Prototype Model.

With all that being said, `this` keyword is very easy concept to understand, and let me show you how.

## Why Do We Need THIS

One way you can see this keyword is as a way to do a 2-dimensional look up in your scope. When you define a variable, the lookup in your scope chain happens from inner to outer functions until you reach the global scope. Now, what if you want one of your variables to look up for data/or-its-value in other parts of your scope? `this` keyword gives us a way to solve it. And there is much more to `this` which we will see in the next part of the series.

Now, you could say that, I could write a function and receive an argument as my data. And you wouldn't be wrong, but that's just another way to solve it.

## Call Site

Call site refers to the location of the function invocation, and it is an important step in determining what the value of `this` keyword is going to be. In some cases, the call-site can get hidden away by libraries and native APIs, e.g., setTimeout, but those cases are limited and predictable.

There is an informal rule that says, whatever is on the left is what this keyword points to. It's a good conclusion to some extent, but nevertheless, how we reach that conclusion is important too.

> 'this' is a run-time binding and not an author-time binding.

## Rules for Call Site

The value of this keyword depends on _how_ the function is invoked. We should now ask ourselves, **how many ways** can a function be invoked in JavaScript? The answer to that question is, there are four ways to invoke a function:

- **Default Binding**

- **Implicit Binding**

- **Explicit binding**

- **new operator Binding**

& then you have your arrow functions. And the value of `this` keyword is determined by those five ways.

In the [next part](/javascript/default-binding-this-keyword-part-2), we will see how [**Default Binding**](/javascript/default-binding-this-keyword-part-2) works.


TIME BUG

Tutorials

They said something about this being the last level of the first chapter... whatever that means!

CLRS Merge Sort in JavaScript

Libraries Aerosailor.com Uses

Merge Sort in JavaScript

Quicksort in JavaScript

Implicit Binding - THIS Keyword — Part-3

Default Binding - THIS Keyword — Part-2

THIS Keyword in JavaScript — Part-1

Subscribe to
Savvy Saturday

TIME BUG

Tutorials

They said something about this being the last level of the first chapter... whatever that means!

CLRS Merge Sort in JavaScript

Libraries Aerosailor.com Uses

Merge Sort in JavaScript

Quicksort in JavaScript

Implicit Binding - THIS Keyword — Part-3

Default Binding - THIS Keyword — Part-2

THIS Keyword in JavaScript — Part-1

Subscribe to Savvy Saturday

Subscribe to
Savvy Saturday