DEV Community: delph

an introduction to Dynamic Programming

delph — Thu, 02 Jul 2020 16:22:25 +0000

what is Dynamic Programming?

Dynamic programming is a way of making your algorithm more efficient by storing some of the intermediate results. It works well when your algorithms has a lot of repetitive computations.

In Dynamic Programming there are typically three steps you can take:

Come up with a recursive solution to the problem
Store or memoize the intermediate results if there are a lot of repeated computations
Come up with a bottom-up approach

Recursive solution for fibonacci sequence

If we want to write a function fib(n) to find the nth number of a Fibonacci sequence.

Given the following Fibbonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, ... fib(3) should return 2 and fib(6) should return 8.

A recursive solution to the problem without memoization:

function fib(n) {
  if (n === 1 || n === 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

The above solution works, but it is very inefficient.

From the diagram above, it can be seen that in order to calculate the 5th fibonacci number, fib(5), we need to first compute fib(4) and fib(3) and add them up. In order to compute fib(4), we then need to compute fib(3) again and fib(2).

Hence it can be seen that there are a number of repeated computations, where we need to compute the return value for fib(2) three times, and fib(3) two times.

This becomes an issue when the value of n increases (eg. fib(1000)) and the time to calculate the nth Fibonacci grows exponentially, with a time complexity of O(2^n).

With Dynamic programming, we can store (ie. memoize) the return value of say, fib(3) after it is computed, and then use that value when it is needed again.

We can tweak the solution as follows:

Use an array with a length of n + 1 , where the initial values are all set to null
Store the return value for fib(n) at index n of the array. (ie. 1, which is the return value of fib(1), will be stored at array[1])
At the beginning of the function, check whether the array[n] is null or not. If it is not null, it means that we have already stored the return value at index n, so we can just return array[n]. If it is not null, then we need to find the sum of the previous two Fibonacci numbers. and then store that result in array[n]

Rewriting the solution using memoization:

function fibWithMemoization(n) {
  const memo = new Array(n + 1).fill(null);

  function fib(n) {
    if (memo[n] !== null) {
      return memo[n];
    }
    if (n <= 2) {
      return 1;
    } else {
      result = fib(n - 1) + fib(n - 2);
      memo[n] = result;
      return result;
    }
  }

  return fib(n);
}

This reduces the time complexity to O(n), however there is also a space complexity of O(n)

Also, as n increases, there is a possibility of a recursion error, which happens when there are too many calls on a call stack. To fix that, a bottom-up approach can be used.

Bottom-up approach

In the bottom-up approach, we start from the smallest sub-problem and work our way up. In this case, we iterate up to n and store the earlier results in a table/ array.

function fib(n) {
  if (n === 1 || n === 2) return 1;
  arr[1] = 1;
  arr[2] = 1;
  for (let i = 3; i <= n; i++) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }
  return arr[n];
}

With the bottom-up approach, the time complexity is O(n) and space complexity is constant.

quick beginner's guide to Golang

delph — Sun, 28 Jul 2019 16:40:46 +0000

Go

Go language, or Golang, is a statically-typed, compiled programming language initially developed at Google in 2007. It provides garbage collection, type safety, dynamic-typing capability, and other advanced built-in types such as variable length arrays and key-value maps.

format of a typical Go file, `main.go`

package main // declare package name, this line is mandatory

import "fmt" // import packages

func main(){
    fmt.Println("Hello World")
}  // every Go program has at least one function, which is main().

to execute it, run
go run main.go

or go build to make an executable file

variables

method 1:

func main(){
    var name string = "Mary"
    var age int = 40
}

method 2 (type inference):

func main(){
    name := "Mary"
    age := 40
}

if... else...

func main(){
    age := 50
    if age > 50 {
        fmt.Println("More than 50")
    } else if age < 50 {
        fmt.Println("Less than 50")
    } else {
        fmt.Println("50 Years Old")
    }
}

arrays

Arrays in Go are fixed-size and can be created like this var variable_name [SIZE] variable_type

func main(){
// declaring arrays
    var a [5] string // ["", "", "", "", ""]
// initializing arrays
    fruits := [5]string{"banana", "orange", "apple", "kiwi", "mango"} 
    // ["banana", "orange", "apple", "kiwi", "mango"]
}

slice

an abstraction over arrays to create dynamically-sized arrays

func main(){
    ages := []int{10, 20, 35, 40, 50} // [10, 20, 35, 40, 50]
    ages = append(ages, 60) // adds an element. original slice is not modified, a new one is returned
}

maps

Maps hold key-value pairs, much like dictionaries in Python. to create a map, use the built-in 'make' function

func main(){
    // create map
    ages := make(map[string]int)

    ages["Mary"] = 40
    ages["Pete"] = 30
    ages["Nick"] = 25

   // to delete something from map, use delete function
   delete(ages, "Pete")
}

loops

the only type of loop in Golang is the 'for' loop

func main(){
    for i := 0; i < 5; i++ {
        fmt.Println(i)
    }   

    // using a 'while loop' style
    j := 0

    for j < 5 {
       fmt.Println(j)
       j++
   }

    // printing items in an array using range
    fruits := []string{"banana", "orange", "grape"}

    for index, value := range fruits {
        fmt.Println("index:", index, "value:", value)
        /* index: 0 value: banana
           index: 1 value: orange
           index: 2 value: grape */               
    }

    // printing items in a map using range
    ages := make(map[string]int)

    ages["Mary"] = 40
    ages["Pete"] = 30
    ages["Nick"] = 25

    for key, value := range fruits {
        fmt.Println("name:", key, "age:", value)
        /* name: Mary age: 40
           name: Pete age: 30
           name: Nick age: 35 */               
    }
}

functions

func main(){
    result := sum(10, 5)
    fmt.Println(result) // 15
}

// simple function, return type is specified after parameter list
func sum(int a, int b) int {
    return a + b
}

a Go function can return multiple types. this can be useful for error handling as Go doesn't have exceptions like other languages.

import (
    "fmt"
    "errors"
    "math"
)

func main(){
    result, err := sqrt(4)
    if err != nil {
        fmt.Println(err)
    } else {
        fmt.Println(result)
    }
}

func sqrt(x float64) (float64, error) {
    if x < 0 {
        return 0, errors.New("Undefined for negative number")
    }
    return math.Sqrt(x), nil
}

struct

a struct is a collection of fields so that you can group things together to create a more logical type.

type person struct {
    name string
    age int
}

func main(){
    p := person{name: "Nick", age: "25"}

    // use dot notation to access a member of a struct
    fmt.Println(p.age) // 25
}

pointers

Every variable is stored in memory and we can get the memory address of the variable by using the ampersand (&) operator.

func main(){
    i := 10
    fmt.Println(&i) // prints memory address
    inc(i)
    fmt.Println(i) // 10

}

func inc(x int) {
    x++
}

in the above example, the inc function is not going to do anything because i is copied by value so the inc function gets a copy of i and the original version is not modified.

however, if we pass a pointer to the variable then the function is able to look at the value at that memory reference and modify the original version.

we can accept a pointer by prefixing the type with an asterisk (*) and send the pointer using an ampersand (&). inside the inc function, we need to add another asterisk to dereference the pointer

func main(){
    i := 10
    inc(&i)
    fmt.Println(i) // 11

}

func inc(x *int) {
    *x++
}

handling asynchronous actions with redux-thunk

delph — Tue, 09 Jul 2019 15:23:14 +0000

* this article assumes some basic knowledge in redux

Redux

Redux is a library commonly used for managing global state in React applications. Redux works great for state updates for synchronous actions (eg. incrementing/ decrementing a counter), but more often that not, most applications will need to perform some sort of asynchronous action (eg. making an API call to fetch data from the server).

redux-thunk

redux-thunk is a middleware that allows you to write asynchronous logic that interacts with the store. A redux middleware, as the name suggests, sits in the middle between the moment an action is dispatched, and the moment it reaches the reducer.

getting started

first, create your react app and install dependencies

npm install redux react-redux redux-thunk axios --save

yarn add redux react-redux redux-thunk axios

index.js

In your root index.js file, import the Provider from 'react-redux' as per normal and wrap the App component with it so that the entire app has access to the redux store.

We will also need to import createStore from 'redux' as per normal. The only difference is that we also need to import applyMiddleware, a function from 'redux', and thunk from 'redux-thunk'. This will be passed in as the second argument when we create the store, so that whenever we dispatch an action, the action will be first sent to redux thunk as the middleware.

// src/index.js

import React from 'react';
import ReactDOM from 'react-dom';
import { Provider } from 'react-redux';
import { createStore, applyMiddleware } from 'redux';
import thunk from 'redux-thunk';

import App from './components/App';
import reducers from './reducers';

const store = createStore(reducers, applyMiddleware(thunk));

ReactDOM.render(
  <Provider store={store}>
    <App />
  </Provider>,
  document.querySelector('#root')
);

At this point, we will get some errors since we have not created our 'App' component and reducers. but first, let's do some configuration and create some action creators to fetch our data.

API configuration

While this step is not necessary, is is useful to create an axios instance and specify a base URL in an apis folder. By pre-configuring axios, we do not need to specify the base each time we make a request.

For this example, we will be fetching a list of posts from jsonplaceholder.

// src/apis/jsonPlaceholder.js
import axios from 'axios';

export default axios.create({
  baseURL: 'https://jsonplaceholder.typicode.com'
})

action creators

the main difference between normal synchronous applications and asynchronous actions with redux thunk lies in this step.

generally, for redux, an action creator is simply a function that returns a plain javascript object with a type property (and occasionally some other properties such as 'payload' etc.)

with redux thunk, an action creator can also optionally return a function instead of an action object. our action creator to fetch posts would then look something like this:

// src/actions/index.js
import jsonPlaceholder from '../apis/jsonPlaceholder';

// normal action creator
export const clearPosts = () => ({
    type: 'CLEAR_POSTS'
})

// thunk action creators
export const fetchPosts = () =>  async dispatch => {
  const response = await jsonPlaceholder.get('/posts')

  dispatch({type: 'FETCH_POSTS', payload: response.data})
 }

export const fetchUser = id =>  async dispatch => {
  const response = await jsonPlaceholder.get(`/users/${id}`)

  dispatch({type: 'FETCH_USER', payload: response.data})
 }

in addition to the dispatch argument, we can optionally pass in a second argument, getState, which would give us total control over changing or getting information out of our redux store.

// src/actions/index.js

export const fetchPostsAndUsers = id =>  async (dispatch, getState) => {
  await dispatch(fetchPosts())

  const userIds = _.uniq(_.map(getState().posts, 'userId'))

  userIds.forEach(id => dispatch(fetchUser(id)))
 }

reducers

nothing too different here.

// src/reducers/index.js
import { combineReducers } from 'redux';
import postsReducer from './postsReducer';
import userReducer from './userReducer';

export default combineReducers({
  posts: postsReducer,
  users: userReducer
});

// src/reducers/postsReducer.js
export default (state = [], action) => {
  switch (action.type) {
    case 'FETCH_POSTS':
      return action.payload;
    default:
      return state;
  }
};

// src/reducers/userReducer.js
export default (state = [], action) => {
  switch (action.type) {
    case 'FETCH_USER':
      return [...state, action.payload];
    default:
      return state;
  }
};

finally, our App.js

as per normal redux, we need to import connect from 'react-redux' in order to access the state in our redux store.

// src/components/App.js

import React from 'react';
import { connect } from 'react-redux';
import { fetchPosts } from '../actions';

class App extends React.Component {
  componentDidMount() {
    this.props.fetchPosts();
  }

  renderList() {
    return this.props.posts.map(post => {
      return (
        <div key={post.id}>
          <h2>{post.title}</h2>
          <p>{post.body}</p>
        </div>
      );
    });
  }

  render() {
    return <div>{this.renderList()}</div>;
  }
}

const mapStateToProps = state => {
  return { posts: state.posts };
};

export default connect(
  mapStateToProps,
  { fetchPosts }
)(App);

functional programming with javascript

delph — Tue, 11 Jun 2019 05:52:30 +0000

what is functional programming?

Functional programming follows a few core principles:

Pure functions, ie.
- the same input always gives the same output
- limited side effects: any changes, or mutations, to the state of the program outside the function are carefully controlled
Function composition: build a complex system by combining more basic components/ functions

In languages that support functional programming (like JavaScript, Ruby, Scala, etc), functions are first-class objects. This means that functions can be assigned to a variable, passed into another function as arguments, or returned from another function just like any other normal value.

Imperative vs declarative

Functional programming is a form of declarative programming. This means that you tell the computer what to do, rather than how to do it (ie. the how gets abstracted away).

This can be done by calling methods or functions. JavaScript offers many predefined methods that handle common tasks so we do not need to write out how the computer should perform them. For example, instead of writing a for loop, the map method can handle the details of iterating over an array.

An advantage of this is that it helps to avoid semantic errors, like the "Off By One Errors".

Mutating vs non-mutating methods

In functional programming, a function should not cause side effects by altering any variable or object in the code. (ie. a function should be non-mutating).

In frameworks/ libraries like React and Redux, a core principle is that you should not mutate the state.

slice, map, filter, reduce, concat are some non-mutating methods in JavaScript (ie. these methods return a new array)
splice, push, pop, sort are mutating (ie. these methods change the original array)

TIP: .slice() is an easy way to make a copy of the entire array. With ES6 (and beyond), you can also use the spread operator to easily make a copy of an array or object.

const array = ['a', 'b', 'c'];
const object = {message: 'hello world'};

// ES5
const newArray = array.slice();
const newObject = Object.assign({}, object);

// Spread operator
const newArray2 = [...array];
const newObject2 = {...object};

TIP: To sort an array, concatenate an empty array to the one being sorted (since concat returns a new array), then run the sort method.

const array = [1 , 4, 5, 3]

const newArr = array.concat([]).sort()

console.log(array) // [1, 4, 5, 3]
console.log(newArr) // [1, 3, 4, 5]

Currying and Partial Application

The arity of a function is the number of arguments it requires. Currying a function means to convert a function with multiple arguments into a series of functions with a single argument (ie. from arity of N into N functions of arity 1)

In other words, it restructures a function so it takes one argument, then returns another function that takes the next argument, and so on.

//Un-curried function
const add = (a, b) => a + b

//Curried function
const curriedAdd = a => b => a + b

curriedAdd(1)(2) // Returns 3

Currying allows for function composition and gives us the ability to create reusable functions. In cases where all the arguments to a function cannot be supplied at one time, we can save each function call into a variable. That variable will hold the returned function reference that takes the next argument when it's available.

Similarly, partial application applies a few arguments to a function at a time and returns another function that takes fewer arguments.

understanding 'this'

delph — Thu, 27 Dec 2018 07:33:33 +0000

What is 'this'?

In short, this in JavaScript references the object that is executing the current function.

How then do we determine the object being referenced?

(#1.) If the function is part of an object (ie. a method), `this` references the object.

const bird = {
  name: "Tweety",
  printThis() {
    console.log(this); // `this` references `bird`
  }
};

bird.printThis(); // { name: 'Tweety', printThis: ƒ }

(#2.) If the function is a regular function (not part of an object), `this` references the global object in the running environment (ie. window in browsers and global in node)

function bird() {
  console.log(this);
}

// If called in browser:

bird(); // Window {stop: ƒ, open: ƒ, alert: ƒ, ...}

Note: if a method has a callback function, this in the callback function references the global object.

const bird = {
  birdName: "tweety",
  sounds: ["chirp", "quack", "tweet"],
  printBirdSounds() {
    this.sounds.forEach(function(sound) {
      console.log(this.birdName, sound);
    });
  }
};

bird.printBirdSounds(); // undefined 'chirp'
// undefined 'quack'
// undefined 'tweet'

In the above example, this.sounds in the printBirdSounds() method correctly references the bird object as it follows rule 1 above.

However, as the line logging this.birdName is inside a regular function, this now follows rule 2 and references the global object. Since there is no birdName property on the global object, it prints undefined.

To fix this, see rule 4 below.

(#3.) If the function is called using the `new` keyword in the case of constructor functions, `this` references a new empty object.

function Bird() {
  console.log(this);
  this.name = "tweety";
  console.log(this);
}

new Bird();
// {}
// { name: 'tweety' }

(#4.) If `this` is used in an arrow function, the value of this is inherited from its enclosing scope (ie. follow lexical scoping rules).

This is because arrow functions do not have their own this value.

Rewriting the second example in rule 2 using arrow functions,

const bird = {
  birdName: "tweety",
  sounds: ["chirp", "quack", "tweet"],
  printBirdSounds() {
    this.sounds.forEach(sound => console.log(this.birdName, sound));
  }
};

bird.printBirdSounds(); // tweety 'chirp'
// tweety 'quack'
// tweety 'tweet'

With arrow functions, the line logging this.birdName now follows rule 1 and references the bird object!

(#5.) If `bind`, `call`, `apply` are used to call a function, `this` inside the function is the object that is passed in as the argument.

function bird() {
  console.log(this);
}

const tweety = {
  sound: "tweet"
};

const bindTweety = bird.bind(tweety);
bindTweety(); // { sound: 'tweet' }
bird.call(tweety); // { sound: 'tweet' }
bird.apply(tweety); // { sound: 'tweet' }

understanding closures in javascript

delph — Wed, 26 Dec 2018 18:02:17 +0000

Closures

Closures are created when you define a function. A closure encompasses everything that a function can access.

var g = "G";

function functionA() {
  var a = "A";

  function functionB() {
    var b = "B";
    console.log(a, b, g);
  }

  functionB(); // prints A, B, G

  a = "Batman";
  functionB(); // prints Batman, B, G
}

functionA();

In the above example, when functionB is defined, its created closure gives it access to the global variable 'g', the variable 'a' and the variable 'b'.

Note that the closure gives a reference to the variable and not a copy of the variable. Hence, if the value of variable 'a' is changed and functionB is called again, the new value of 'a' will be printed instead of the old one.

Closure is a very important concept in functional programming paradigm. It allows a function to remember its context where it's defined.

When a function returns another function, the concept of closures becomes more relevant. The returned function has access to variables that are not in the global scope, but solely exist in its closure ie. private variables.

In the above example, the variable 'a' is considered private in the function and only accessible by functionB.

In functional programming, closures are also frequently used for partial application and currying.

Partial Application: The process of applying a function to some of its arguments. (ie. a function that takes a function with multiple parameters and returns a function with fewer parameters.)

Currying: A function that takes a function with multiple parameters as input and returns a function with exactly one parameter.

Here is another example:

function adder(a) {
  function add(b) {
    return a + b;
  }

  return add;
}

var addOne = adder(1); // a is 1, addOne has a reference to add(b)
var addTen = adder(10); // a is 10

addOne(5); // 1 (a) + 5 (b) = 6
addTen(5); // 10 (a) + 5 (b) = 15

In C and most other common languages, after a function returns, the local variables are no longer accessible because the stack-frame is destroyed.

In JavaScript, if you declare a function within another function, the inner function can remember and access variables and arguments of its outer function, even after the outer function has returned.

For further reading...

https://medium.com/javascript-scene/master-the-javascript-interview-what-is-a-closure-b2f0d2152b36
https://medium.com/dailyjs/i-never-understood-javascript-closures-9663703368e8
https://medium.freecodecamp.org/whats-a-javascript-closure-in-plain-english-please-6a1fc1d2ff1c

An intro to TypeScript

delph — Fri, 21 Dec 2018 11:20:33 +0000

What is TypeScript

TypeScript is a superset of JavaScript that compiles to plain JavaScript. TypeScript is pure object oriented with classes, interfaces, and module-statements just like in Java or C#.

Unlike JavaScript, which is a loosely-typed language,TypeScript supports static typing.

Some advantages

Self-documenting: Instead of adding comments to your code, with a type system you are annotating your code and it will always be in sync with the actual code
Avoid common pitfalls: TypeScript is going to spit out any compilation error unlike JavaScript which is an interpreted language. You can catch errors at the early stage during development, and less bugs = Win

Basic types

const name: string = "Jane";
const age: number = 40;
const isAlive: boolean = true;

isAlive.indexOf("Jane"); // will show an error since indexOf cannot be called on a boolean

Alternatively, this will also work:

const name = "Jane";
const age = 40;
const isAlive = true;

isAlive.indexOf("Jane"); // will also throw an error

Arrays

let food: string[];
food = ["cookie", "milk", "biscuit"];
food.push("donut");

food = [1, 2, 3]; // will throw an error
food.push(true); // will also throw an error

Functions

The function below takes in a parameter (word) with type string and returns a string.

function reverse(word: string): string {
  return word
    .split("")
    .reverse()
    .join("");
}

reverse("racecar"); // this is ok
reverse(true); // this will throw an error

We can omit the return type because the compiler can infer the return type. Hence this will also work:

function reverse(word: string) {
  return word
    .split("")
    .reverse()
    .join("");
}

Interfaces

An interface defines the syntax (eg. properties, methods) that members of the interface must adhere to.

Interfaces contain only the declaration of the members. It is the responsibility of the deriving class to define the members.

interface Person {
  name: string;
  age: number;
}

function birthYear(person: Person) {
  return 2018 - person.age;
}

Aliases

Type aliases create a new name for a type.

type Vegetable = "broccoli" | "carrot";
// the '|' is a union type, which means that Vegetable can be either a 'broccoli' or 'carrot'

type Fruit = "apple" | "banana" | "kiwi";

type Ingredient = Vegetable | Fruit; // chaining union types

const juice: Ingredient[] = ["broccoli", "kiwi"];
// probably a terrible juice but still valid in TypeScript

const juice2: Ingredient[] = ["broccoli", "bread"];
// will throw an error since bread is not a fruit or vegetable

To get started

Install - For NPM users:

npm install -g typescript

Name your file with a '.ts' extension. For example, 'helloworld.ts'
Write your code
Compile your code by typing tsc helloworld.ts in the command line. If all goes well, a JavaScript file helloworld.js will be generated!

TypeScript in your React applications

Create-React-App now has built-in support for working with TypeScript!

To create a new project, simply type:

npx create-react-app my-typescript-app --typescript

To add TypeScript to an existing application:

npm install --save typescript @types/node @types/react @types/react-dom @types/jest

Next, rename any file to be a TypeScript file (e.g. src/index.js to src/index.tsx) and restart your development server!

sorting algorithms in javascript

delph — Thu, 20 Dec 2018 07:07:52 +0000

Bubble sort

Fun fact: if you say bubble sort really fast, it sounds like bulbasaur :O

Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order.

The pass through the list is repeated until no swaps are needed, which indicated that the list is sorted.

This algorithm is not suitable for large data sets as its average and worst case time complexity are of O(n*2).

even Obama disapproves

The best case time complexity is Ω(n) which occurs when array is already sorted.

function bubbleSort(arr) {
    let swapped, tmp;
    do {
        swapped = false;
        for (let i=0; i< arr.length -1 ; i++) {
            if(arr[i] > arr[i+1]) {
                tmp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = tmp;
                swapped = true;
            }
        }
    } while (swapped)
    return arr
}

Selection sort

Selection sort is a simple sorting algorithm that loops over the array and saves the absolute lowest value. The lowest value is then swapped with the first item in the unsorted array.

The best and worst case time complexity is O(n*2).

function selectionSort(arr) {
    for (let i =0; i < arr.length; i++) {
        let min = i
        for (let j=i+1; j<arr.length; j++) {
            if (arr[j] < arr[min]) {
                min = j
            }
        }
        if (i !== min) [arr[i], arr[min]] = [arr[min], arr[i]]
    }
    return arr
}

Insertion sort

With insertion sort, you move an element that is not in the right position all the way to the point that it should be.

This algorithm is not suitable for large data sets as its average and worst case time complexity are of O(n*2). The best case time complexity is Ω(n) which occurs when array is already sorted.

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i ++) {
        for (let j =0; j < i; j++) {
            if (arr[i] < arr[j]) {
                let tmp = arr.splice(i, 1)
                arr.splice(j,0,tmp[0])
            }
        }
    }
    return arr
}

Merge sort

Merge sort splits an array into halves, calls itself for the two halves, and then merges the two halves.

The merge algorithm consists of two functions: the mergeSort function, which takes care of partitioning the arrays, and the merge function, which merges the separated arrays.

here is a visual representation

Merge sort leverages on recursion and is one of the most respected searching algorithms. Its worst time complexity is O(n*logn(n)). However, the best case time complexity is also Ω(n*logn(n))

function mergeSort(arr) {
  if (arr.length === 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  let li = 0; //left index
  let ri = 0; //right index
  while (li < left.length && ri < right.length) {
    if (left[li] < right[ri]) {
      result.push(left[li]);
      li++;
    } else {
      result.push(right[ri]);
      ri++;
    }
  }
  return result.concat(left.slice(li)).concat(right.slice(ri));
}