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


## AWS Account Creation

The first thing we need to have is access to AWS. You will have to sign up and provide your credit
card details for account creation. I created myself a new AWS account, incase I face any issue I can
highlight possible solutions to you.

After creating my fresh new account, it looks something like this on my landing page. Hope it looks
somewhat similar for you as well.

## Getting Started

AWS Lambda is essentially a language-specific environment that runs in an execution environment
called as runtime. This runtime passes events, context information and responses between other
lambdas as well.

### Install Python & PIP

Python should be most probably installed on your computer. You can test by running
`python --version` or `python3 --version`. You can install Python from here:
https://www.python.org/downloads/

Try running `pip --version` if its installed, if not then you can install it from here:
https://pip.pypa.io/en/stable/installation/

### Installing Docker

I installed Docker on my iMac using the GUI package as it would handle setting all the configuration
and path correctly. There is a CLI option as well but I wouldn’t recommend it unless the GUI package
is unable to install for you. Docker’s download page > https://docs.docker.com/desktop/

### Installing AWS CLI

We would need the AWS CLI to push the docker container to the AWS ECR which is just a registry or
repository for storing the images. I again used the GUI installer from here >
https://docs.aws.amazon.com/cli/latest/userguide/getting-started-install.html

## Lets Create Our Codebase

### Create Dockerfile

```docker
# source the base image
FROM public.ecr.aws/lambda/python:3.9

# copy function code
COPY app.py ${LAMBDA_TASK_ROOT}

# each required library is listed as a separate line
COPY requirements.txt  .
RUN  pip3 install -r requirements.txt

# set the cmd to the handler
CMD ["app.handler"]
```

### Create Lambda Function

We will create a simple function that returns the parameter it receives. This way will get to see
what information does our lambda function has available when it begins to run.

- **Event** is a dict that contains the parameters which are sent when the function is invoked
- **Context** param is the context in which the function is called

```python
import jsonpickle

def handler(event, context):
	return {
		"EVENT": jsonpickle.encode(event),
		"CONTEXT": jsonpickle.encode(context)
	}
```

### Create requirements.txt

```txt
jsonpickle==1.3
```

## Running Lambda Container Locally

### Build

```shell
docker build -t <container-name> .
```

e.g. if we name our container raring-rusty then the cmd will look like:

```shell
docker build -t raring-rusty .
```

After the build is complete, we can quickly verify by hitting the following command.

```shell
docker images
```

It should output something like this:

```shell
➜ docker images
REPOSITORY     TAG       IMAGE ID       CREATED        SIZE
raring-rusty   latest    a0ea76e99b97   1 minute ago   595MB
```

Before we can run the docker, we have to install a Runtime Interface Client which defines a HTTP
interface for runtimes to receive invocation events from Lambda and respond.

### Install RIC

```shell
pip install awslambdaric
```

### Running

```shell
docker run -p 9000:8080 <container-name>:latest
```

e.g.

```shell
docker run -p 9000:8080 raring-rusty:latest
```

## Testing Lambda Invocation

### Using Postman

You can install Postman from here: https://www.postman.com/ and test the lambda function before
deploying it to AWS ECR

### URL

```url
http://localhost:9000/2015-03-31/functions/function/invocations
```

### Method

```txt
POST
```

### Body -

- Select `raw` as the body type and `json` as the format

```json
{ "is_cat": "true" }
```

### Authorization

```txt
No Auth
```

### Using CURL

```shell
curl -XPOST "http://localhost:9000/2015-03-31/functions/function/invocations" -d '{"is_cat":"true"}'
```

### Result

At this point you should get a response back from your lambda function. Mine looked like below:

```json
{
  "EVENT": "{\"is_cat\": \"true\"}",
  "CONTEXT": "{\"_epoch_deadline_time_in_ms\": 1657690206053, \"aws_request_id\": \"048c7493-7487-4af8-9b28-6a774ccfad8c\", \"client_context\": null, \"function_name\": \"test_function\", \"function_version\": \"$LATEST\", \"identity\": {\"cognito_identity_id\": null, \"cognito_identity_pool_id\": null, \"py/object\": \"awslambdaric.lambda_context.CognitoIdentity\"}, \"invoked_function_arn\": \"arn:aws:lambda:us-east-1:012345678912:function:test_function\", \"log_group_name\": \"/aws/lambda/Functions\", \"log_stream_name\": \"$LATEST\", \"memory_limit_in_mb\": \"3008\", \"py/object\": \"awslambdaric.lambda_context.LambdaContext\"}"
}
```

In next part, let’s look at how we can push our docker image to AWS ECR i.e. Elastic Container
Registry to which our AWS Lambda will point.


Deploy Python Lambda functions with Docker


## 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.


How I Built My Website

Introduction to Algorithms by CLRS version of Merge Sort