Forem: Jenny Yang

Nesting GraphQL with MongoDB

Jenny Yang — Wed, 04 Nov 2020 20:45:11 +0000

Getting Started

GraphQL, Apollo server and MongoDB all connected on your app.
Dependencies to install
devDependencies are optional, only for the sake of your convenience.

// package.json
{
  "name": "server",
  "version": "1.0.0",
  "description": "",
  "main": "index.js",
  "scripts": {
    "start": "nodemon --exec babel-node src/index.js"
  },
  "keywords": [],
  "author": "",
  "license": "ISC",
  "dependencies": {
  "apollo-server-express": "^2.19.0",
  "express": "^4.17.1",
  "graphql": "^15.4.0",
  "mongoose": "^5.10.11"
  },
  "devDependencies": {
    "@babel/cli": "^7.12.1",
    "@babel/core": "^7.12.3",
    "@babel/node": "^7.12.1",
    "@babel/preset-env": "^7.12.1",
    "nodemon": "^2.0.6"
  }
}

How it works

There are three things to define to use graphQL and the logic might not be specifically applied to MongoDB + graphQL. The logic is simple.

Let MongoDB how your schemas look like
Let GraphQL how your schemas look like
Let Apollo Server how you are going to use these schemas

Logic 1. Defining MongoDB Schema

We are making Transaction schema looking like this:

Transaction {
  price
  method
  cardNumber
  paidTime
  items: [
    {
      amount
      quantity  
    }
  ]
}

We are going to use mongoose as ORM for MongoDB. You just need to define its data type and any additional options if any. It is also very simple. You just define each schema and put them together. MongoDB Schema would look like this:

import mongoose from 'mongoose';
const Schema = mongoose.Schema;
const itemSchema = new Schema({
  amount: { type: Number },
  quantity: { type: Number },
});

const transactionSchema = new Schema({
  price: { type: Number, required: true },
  method: { type: String, default: 'VISA', required: true },
  cardNumber: { type: String, required: true },
  paidTime: { type: Date, default: new Date(), required: true },
  items: [itemSchema],
});

export const Transaction = mongoose.model('Transaction', transactionSchema);

Break down

Import mongoose
Create a schema instance for item (itemSchema)
Create a schema instance for transaction (transactionSchema)
put itemSchema into items property of transactionSchema object

Notice itemSchema is going to be part of transactionSchema as an array.

Logic 2. Defining TypeDefs

Let's create a type definition. We are going to use Apollo Server as middleware to handle graphQL. There are other middlewares such as graphql yoga, but Apollo Server is a standard.
Query does things corresponding to GET request, Mutation takes care of any other requests that cause mutation of data such as POST, PUT and DELETE. We are starting by Mutation, because we will push data first, and then fetch them to check if the data properly saved.

There are four type definitions I used in this tutorial:
type SchemaName {types} : Defining schema type
input nameOfInput {types} : Defining schema's input, used to type argument's type
type Query {types}: Defining query structure matching to your resolver
type Mutation {types}: Defining mutation structure matching to your resolver

// typeDefs.js

import { gql } from 'apollo-server-express';

export const typeDefs = gql`
  scalar Date

// Defining your Query

// 1 Defining your graphql schema type
  type Item {
    id: ID!
    amount: Float
    quantity: Int
  }

  type Transaction {
    id: ID!
    price: Float!
    method: String!
    cardNumber: String!
    paidTime: Date!
    items: [Item]
  }

  // 2 Defining input type
  input ItemInput {
    transactionId: String!
    amount: Float
    quantity: Int
  }

  input TransactionInput {
    price: Float!
    method: String!
    cardNumber: String!
    items: [ItemInput]
  }

  // 3 Defining your Muation
  type Mutation {
    createTransaction(TransactionInput: TransactionInput!): Transaction
    createItem(ItemInput: ItemInput): Transaction

`;

Note:! mark means this field is required, notice createItem returns Transaction schema

Break down

defined Schema of Item and Transaction
defined type of argument which going to be passed into Mutation function
defined two functions to create transaction and to create item.

Logic 3. Defining how you are going to create or update api

Resolver is a function to handle populating your data into your database, you can define how you are going to fetch data and how you are going to update, create data. Since Apollo-server reads from schema from typeDefs, they will need to match how it is structured.
Basic Resolver Structure

const resolver = {
  Query: {
    some async function 
  },

  Mutation: {
    some async function
  }
}

Let's create resolver file for function and you will need to pass it to the apollo server instance. In the Mutation object, add code like so:

Transaction mutation (parent schema)

import { Transaction } from '../models/transaction';
export const transactionResolver = {
  Mutation: {
    createTransaction: async (
      _, { TransactionInput: { price, method, cardNumber } }
    ) => {

      const newtransaction = new Transaction({
        price,
        method,
        cardNumber,
      });

      await transaction.save();

      return newtransaction;
    },
  },
}

Firstly, createTransaction is an async function, takes a few arguments but we only care about the second argument which is what we are going to push to the database and its type.
Secondly, create a Transaction instance imported from mongoose model with input arguments (price, method, cardNumber) then save the instance using mongoose.
Finally, return the instance.
Item resolver (child schema)

import { Transaction } from '../models/transaction';
export const itemResolver = {
  Mutation: {
    createItem: async (
      -, {ItemInput: {transactionId, amount, quantity} }
    ) => {
      // find the transaction by id
      const transaction = await Transaction.findById(transactionId);

      // check if the transaction exists
      if (transaction) {
         // if exists, push datas into items of transaction
         transaction.items.unshift({
           amount,
           quantity
         });
      } else throw new Error('transaction does not exist');

Create transaction

Now let's create a transaction! You can open up graphql testing playground at your localserver/graphql

mutation {
   functionName(input arguments) { 
     data you want to return, you can be selective
   }
}

Create Items

You can push items into a transaction that you selected with id.

Remember, the transactionId should exist in your database.

Fetching query

// typeDefs.js
import { gql } from 'apollo-server-express';
export const typeDefs = gql`
  scalar Date
// Defining your Query
  type Query {
    transactions: [Transaction!]!
  }
// Defining your graphql schema type
  type Item {
    id: ID!
    amount: Float
    quantity: Int
  }

  type Transaction {
    id: ID!
    price: Float!
    method: String!
    cardNumber: String!
    paidTime: Date!
    items: [Item]
  }
`;

Type definition of Item Shcema

Type definition of Transaction Schema (notice Item type definition is nested in Transaction type definition in items field)
Create Query type that fetches an array of transaction

Transaction Resolver

import { Transaction } from '../models/transaction';
export const transactionResolver = {
  Query: {
    transactions: async () => {
      try {
        const transactions = await Transaction.find()
        return transactions;
      } catch (error) {
         throw new Error(error);
      }
    },
  },
  Mutation: { mutation code ... }
}

Define an async function corresponding to the one in our typeDefs. We defined transactions in Query type in our typeDefs like so:

// typeDef.js - our Query type
type Query {
    transactions: [Transaction!]!
  }

Now let's fetch data in our localhost:port/graphql. Easy peasy. Isn't it? If you are querying data, you can omit query at the beginning of the object as the image below.

query {
  transactions {
     id
     method
     cardNumber
     PadTime
     items {
       id
       amount
       quantity
     }
   }
}

Conclusion

Nesting schema is easy, however, we need to be precise how we want it to be. If things are not working check whether your schema field's names are matching with the one in your resolver and its structure.

Learning Algorithms - Heap | Part 02

Jenny Yang — Mon, 19 Oct 2020 19:58:08 +0000

Continuing from the last post, Heap Part 01, I would explain heap sort which happens when inserting and deleting items from a heap. Let me recap from what I covered last time. We were doing a min-heap example and its basic methods such as parent(), left_child(), right_child().

Learning algorithms - Heap | part 01

Jenny Yang ・ Oct 18 ・ 4 min read

#computerscience #algorithms #heap #datastructures

Violation

Violation in a heap is when a child node is greater than a parent node in max-heap or child node is less than a parent node in min-heap.

Insertion

We are going to have a look a trivial example of how items inserted, to understand the heap sort. To start with, we are going to insert 7, 1, 3 in the order.

insert(7)
insert(3)
insert(1)

Did you notice? every time we inserted an item, there will be a comparison of two items, a parent and child, and swap the two when there is a violation. Continuing inserting items from the given example.

insert(20)
insert(11)
insert(9)

We inserted 7, 3, 1, 20, 11 and 9 so far. There has not been any swap in the second round. Moving on to the next round.

insert(3)
insert(15)
insert(4)
insert(13)

We swapped 20 and 15 as 15 is smaller than its parent 20, and moving on to parent node 7, the parent 7 is smaller than its child 15, so it is all sorted.

There are two comparisons 4 and 15, 4 and 7, the number 4 initially inserted in [9] and moved up to [2] as it is swapped with its parent each time. Last round is to insert 13, hang in there till the end.

Final result

Extract min

Extract min is the deletion method in a heap. In a big picture, there are two steps:

deletion: swap [1] and [n] where n = length of a heap exclude [0] and delete the [n] which is the min item.
heap sort: swap until the item in [1] is smaller than its children.

step 1: deletion

step 2: heap sort

Swap

Swap method is simply swapping two items and will be used in heapify() method.

def swap(self, a, b):
    self.heap[a], self.heap[b] = self.heap[b], self.heap[a]

Heapify

Whenever there is a violation in heap properties, we are going to correct the violation by swapping a child and a parent. What I mean by violation is, when a child is less than its parent in min-heap. There would be two ways of implementation using recursion or iteration. Insertion and deletion always run heapify at the end of the execution to keep to sort the heap.

Iteration

def heapify(self, i):
    parent = i // 2
    """ 
    as long as the element is in the range of index of a heap 
    (0 is not included)
    """
    while i // 2 > 0:
        # if the element is bigger than its parent swap them
        if self.heap[i] < self.heap[parent]:
            self.swap(parent, i)

        # move the index to the parent
        i = i // 2

Let me break down the code line by line.

while i // 2 means as long as the in the range (from 1 to n)
self.heap[i] < self.heap[parent] if the current node is less than its parent, swap those two since parent should be smaller.
i = i // 2 means bubble up to its parent to keep checking the violation.

Note: i in this heapify is self.size which refers to the last index

Recursion

def heapify(self, i):
    l = self.left(i)
    r = self.right(i)
    smallest = i

    """
    if the r and l are within the range of index,
        and if one of those are smaller than i,
        swap them with i
    """
    if l <= self.size and self.heap[l] < self.heap[i]:
        smallest = l
        print(f"now smallest is {self.heap[l]}")
        self.swap(i, smallest)
    if r <= self.size and self.heap[r] < self.heap[i]:
        smallest = r
        self.swap(i, smallest)

    """
    recursively do the process(heapify) above
    until i becomes smallest in the three relationships in the tree
    """
    if smallest != i:
        self.heapify(i)

Break down:

i = parent node
there are three pointers that refer to the left child, right child and smallest. In here, the important thing to remember in here i ≤ l or r.
if l or r are within the range of index and one of those are smaller than i, then swap them with i since i should be the smallest.

recursively do the process until i becomes smallest amongst the three (left child, right child, parent i).

Implementation

The two insertions are basically the same, the argument the heapify method receives varies due to different heapify method. Firstly, appending a new node then increase size. Lastly, sorting the heap.

Insertion: iteration

def insert(self, key):
    self.heap.append(key)
    self.size += 1
    # Fix violation if there is one
    # iteration heapify
    self.heapify(self.size)

In iterative insertion, the heapify takes the last index.

Insertion: recursion

def insert(self, key):
    self.heap.append(key)
    self.size += 1
    # Fix violation if there is one
    # recursion heapify
    self.heapify(self.size // 2)

In recursive insertion, the heapify takes the parent index of the last item.

The time complexity of insertion is appending O(1) + size alteration O(1) + heapify O(log n) = O(log n)

Deletion (extract min)

Code break down:

store the item to delete
swap the root item with the last one
delete the last item that where there is min item
heap sort until it meets the criteria
return the removed item

def extract_min(self):
    popped = self.heap[1]
    # swap last item and the root(min) item
    self.swap(self.size, 1)
    # pop the last item off
    self.heap.pop()
    # reduce size of the heap as an item is deleted
    self.size -= 1
    # sort the heap
    self.heapify(1)
    # return the popped item
    return popped

Easy peasy, yeah?

The time complexity of deletion is swap O(1) + deletion O(1) + size alteration O(1) + heapify O(log n) = O(log n)

Time analysis

Heapify plays a key role in this algorithm. Because other steps in insertion and deletion are constant time, what we really care about is the heapify method. Let me explain why heapify takes logarithmic time.

If N = 9, the heapify will take a maximum of 4 steps in the worst case, therefore the height of the tree would be the time to process the heapify function. Let's substitute the N to logarithm formula.

2³ is roughly equal to 9, hence the heapify is O(log N)

I still have one advanced method to explain. I will see you in part 3!

Learning Algorithms - Heap | part 01

Jenny Yang — Sun, 18 Oct 2020 21:41:33 +0000

In this post, I would like to talk about one of the easiest trees, Heap. Let's crack into it!

Priority Queue

Before understanding Heap, you need to know what Priority Queue is. Priority Queue is an abstract data type(ADT) in which data has priority and the one that has higher priority will be deleted first. It has three primary operations. Hold on, what is an abstract data type? It is data structure like queue and stack.

insert(Q, x) - insert an item with a key x into priority queue Q
max(Q) or min(Q) - return the largest key or the smallest key than any other key in the priority queue Q
extract-max(Q) or extract-min(Q) - Remove the max or min item from the priority queue Q

Heap and Priority Queue

So what is the relationship between Heap and Priority Queue? Priority Queue can be implemented as an array, a linked list and a heap, a heap is the most efficient implementation of it amongst them.

What is Heap?

Types of Heap

There are two types of the heap, max-heap and min-heap. Each type has different criteria to keep the order. In a max heap, key-value of the parent node always bigger than children nodes, and vice versa.

Heap is a type of binary tree (nearly) made to implement a priority queue, to find maximum or minimum value at a constant time - O(1). A heap consists of the parent node and children nodes. Its children shouldn't be greater than or equal to(child ≤ parent) or smaller than or equal to(child ≥ parent) the parent node. Also, a heap allows the same data and we call this data as a key.

Heap is actually an array that can be visualised as a complete binary tree. There is an array A, A=[20, 15, 13, 11, 7, 9, 3, 3, 4, 1], and it can be visualised as below.

Rule: The order of heap

The order heap is filled should be top to bottom and left to right. So the corresponding index would start from the root number 1 to n. It would be easier with visualisation like so:

We have this array size of 11 represents max heap. The heap will start from index 1 for the sake of convenience of implementation, so index 0 is not in use.

Is this a heap?

Let's look at the examples below and guess whether this is a heap or not. Is this tree a heap?

No, it's not a heap. Why? Because the key of the root element is neither of a max value nor key of min value and each node doesn't follow the rule of order as well, so it's against the definition of the heap.

What about this tree below? Is this a heap?

Yes, It is a max heap where the key of the root has a max value.

Is the image below a heap?

Guess what, no! Because each element wasn't filled from the left. There is a violation because of the element with a key 1.

Implementation of Heap

Now we know what a heap is. Time to implement it. Starting with creating a class that generates an array. The index 0 will be not used, it makes the index order simpler.

 def __init__(self):
     self.heap = [0]
     self.size = len(self.heap) - 1

Methods of Heap

Basic methods for heap would be:

parent(i)
left_child(i)
right_child(i)
insert(key)
min() / max()
extract_min() / extract_max() (delete method)
heapify(i)

parent(i)

parent of i = i / 2 using integer division, Let i be an index of the node, then its parent's index would be i / 2. For example, if the i = 3, (index), then its parent is 3 / 2 = 1

It is apparent that index numbers are integer, not a decimal, so we will do the integer division to get the parent. so parent(3) = 1.

left_child(i)

it returns the index of the left child of i, left child = 2 * i. For example, i = 3, i * 2 = 6

right_child(i)

it returns the index of the right child of i, 'right child = 2 * i + 1For example, 'i =1, 2 * i + 1 = 3

def parent(self, i):
    return i // 2

def left(self, i):
    return 2 * i

def right(self, i):
    return (2 * i) + 1

min()

The minimum node in a min-heap is always a root node, hence it returns root item located in the index 1.

def min(self):
    return self.heap[1]

Okay, guys, I am getting tired… I will continue covering heap in part 2. See you until then.

Learning Algorithms - Binary Search

Jenny Yang — Thu, 08 Oct 2020 22:22:50 +0000

Hi guys, If you are familiar with some data structures, it's now time to learn some algorithms. the very basic but very important topic, binary search.

I can code without knowing algorithms, why would I be bothered to learn them?

Of course, you can build software without using algorithms technically and it is not mandatory (I suppose so). However, when you solved your software problem, have you ever questioned yourself "Can I do better?". This is where algorithms come into play, and ultimately, this thought leads you to become a better programmer.

Let me explain why it is important.

Services like Facebook have more than 2.7 billion users, meaning that Facebook engineers presumably have to handle the data of a huge number of users. There are program A and program B to handle those data. Program A takes 1 second to handle each user's data, and 2 seconds for the counterpart. What would be the speed difference between the two programs? Well, you don't even need to calculate them, B takes twice as long as A.

Algorithms are about how efficiently solve a problem, to do that you need to think like computers.
The most widely used algorithms are in search and sort, today I would talk about searching algorithms.

Linear Search

We can't just jump into Binary Search without knowing Linear Search. You must be familiar with this algorithm, that is a method for finding an element within an array using for loop starting from 0 to end of an array. It takes n times as it will check whether the target is in the index each loop this case, from 0 to 5. The time complexity of Linear Search is O(n)

it is seemingly not bad, but can we do better?
Yes, we can make it better by using binary search.

Binary Search

The way it works similar to Linear Search, but the difference is, it will halve of the array, which reduces areas of searching, meaning saving time to search until it found the target.

Let's see this algorithm in real life.

you have a dictionary to find a word, you are looking for the word "glorious". Firstly, you open the dictionary from the middle, and now you are on the M section. Secondly, because the G section is in the front end of the book, no need to look beyond the M section. Thirdly, so you opened again randomly between the beginning and M section and now you are on F section, meaning you will have to look up between F section and M section until you find the G section. You get the idea.

So basically it narrows down your searching region until you found the target.

Let's dive deeper now. we are going to find number 43 from this array [14, 3, 28, 64, 43, 90]. Hold on, we can't really use binary search because it is not in order, it is impossible to figure out ranges of search! Yes… we can only do a binary search when the array is sorted. Let's get it sorted first.

step 1.

So left = 0 and right = arr.length and mid = (left + right) / 2 in this case.

let's check if our current midpoint is the target. Is 28 == 43 true? No! Okay, what do we do now? Because 28 is smaller than 43, we move left pointer to the right of the midpoint.

step 2.

Since we moved left pointer, mid pointer would be again at the middle of left and right, which is now (3 + 5) / 2 = 4 ((left+right) / 2). Let's check again whether we found 43. Is 64(middle) == 43(target) true? No! Then is 64 greater or smaller than 43? 64 is greater than 43. Then we need to move the right pointer to the left of midpoint.

step 3.

Now, the midpoint is at index [3]. So left + right = 6 so midpoint is 6 / 2 = 3. But what if left + right is an odd number that isn't dividable? For example, if left + right is 7 and divides them by 2 gives us 3.5, which is not an integer number that we can use for index. If you are from python background, you will need to use integer divider like so, left + right // 2, which removes decimal point then returns you 3. Is 43(middle) == 43(target) true? Yes, it is! Let's return the mid pointer 3.

How many steps did you take to find 43?

We took 3 steps, if n is a length of the array, we approximately took n/2 steps, which is much shorter than Linear Search, and this will get smaller relative to the size of N, ultimately we are going to save tremendously if the size of N is huge. So we have done half of n work, which can be expressed as 1/2 * 1/2 * 1/2 * 1/2 * 1/2 = log5(Let's assume log base 2). Therefore, the time complexity is O(log2N)

Implementation

There are two ways of implementation in binary search, iterative and recursive. To keep it simple, I will give an iterative example of implementation. In python-like pseudo-code:

def binary_search(arr, target):
  left = 0
  right = arr.length - 1
  while left <= right:
    mid = (left + right) // 2
    # When found target
    if arr[mid] == target:
      return mid
    # When target is less than midpoint value
    elif target < arr[mid]:
      right = mid - 1  # move right pointer to left of mid
    # When target is greater than midpoint value
    else:
      left = mid + 1  # move left pointer to right of mid
  return -1

I hope you find this useful for your computational thinking, I will talk about more of algorithms later! Thank you for reading!

Learning Algorithms - Insertion Sort

Jenny Yang — Thu, 08 Oct 2020 21:59:46 +0000

Sorting

Sorting is one of the concepts of the basic algorithm as important as searching algorithms. There are tons of algorithms to sort items. Why do we need to sort elements? Because problems become easier once elements are sorted. For example, you can find a median in constant time when an array is sorted, meaning that you can use a binary search.

Insertion Sort

If you think of the way to sort most easily in your head, it might be similar to insertion sort. How it works is, basically, it swaps pairs of elements from left to right until they are sorted. We will have a pointer called key that is a point starting from 1.

def insertion_sort(arr):
    n = arr.length
    for i from 1 to n:
        key = arr[i]    # start from arr[1]
        j = i - 1       # j is left element of pair of i

The code above looks like this visually.

Key will traverse from 1 all the way up to the end (n), and j points to 0 (index). Key will move to the right once its left elements are sorted. This rule can be expressed as follows.

def insertion_sort(arr):
    n = arr.length
    for i from 1 to n:
        key = arr[i]    # start from arr[1]
        j = i - 1       # j is left element of pair of i
        # as long as j is greater than or equals to 0 and left 
        # element(arr[j]) of key is bigger than key, 

        while j >= 0 and arr[j] > key:
           # swap: its left item will move to key
           arr[j + 1] = arr[j]
           # j moves down to the left
           j = j - 1
        # once all sorted, move elements 
        # where j stopped lastly
        arr[j + 1] = key

We swapped 9 and 7 because they were unsorted. Because 7 and 9 are sorted, move the key to the right where there is 4. Then compare 9 and 4. 9 is greater than 4 but 4 is on the left-hand side, they should be swapped.

Move 4 down to the left until it is sorted. once a pair is swapped, j moves to the left. In this case, until 4 is placed in arr[0] (specifically on the code, when j becomes -1). Then move the key to the right where there is 5.

Now, key = 5, we need to sort 5 until it goes down to arr[1], let’s do that.

Because key (4) is sorted, move on to elements, the key becomes 1(arr[4]). Keep swapping until 1 is sorted. Then the result will be like below.

Now key = 3, we will swap 9 and 3.

The same process goes on until 3 is in arr[1]

Finally, here we are! All elements in the array are sorted.

Time Complexity of Insertion Sort

Now, it is time to talk about the time complexity of the algorithms. As you might assume, it took so long time for us to get here. In a nutshell, the algorithm is O(n²). Let’s analyse why.

As you can see, (2)*O(1) and (2)*O(N) and (2)*O(N). We can actually ignore the coefficient. Therefore, the time complexity would be 1*N*N = N²

In conclusion, the time complexity of insertion is quadratic time, which is not very efficient. There is a faster way to sort elements though. I will introduce one later. Thanks for reading!

Learning Algorithms - Merge Sort

Jenny Yang — Thu, 08 Oct 2020 08:53:53 +0000

Previously, we had a look of Insertion Sort and implemented it.

However, its worst-case scenario was O(n²), which is really slow isn't it? and I promised you to more sophisticated and faster algorithms to sort an array that is Merge Sort.

Divide and Conquer

So how can we save time for sorting when it comes to a list of elements? The answer is to divide and conquer. I assume you must know binary search at this juncture, where you already started learning algorithms or you can go back to learn binary search. Let me give you a big picture of the whole plan. Firstly, we will have an array of size n, we will call it A. Secondly, We will then divide in a half (until it is not dividable), which will be two arrays Left and Right. Next, the two arrays will be sorted. Lastly, we will merge them in a sorted order back in array A.

Recursion

Unfortunately, to use Merge Sort, we need to know this notoriously confusing concept, so-called recursion. In a nutshell, recursion is a function call that calls itself. Let’s take a look of code right below.

def call_me(arg):
    call_me(arg)
    print(arg)
call_me("I am calling me")

The function call_me(arg) calls itself, then prints arg. What will happen in this case? It will call itself infinitely printing “I am calling me” like a black hole. It will cause, the notorious name of error, stack overflow, which is literally function calls being stacked up and program used up memory spaces to store those calls, so thrown an error. So all we need to do is let this recursion finishing at some point, to do that, we need a condition to end the recursion, we call it base case.

Let me stop this recursion with a base case. the call_me function is taking one more argument, i, that increments by 1 every execution, and if i becomes 5 the function is going to be returned.

def call_me(arg, i):
    if i == 5:  # if i == 5, return
        return

    i += 1
    call_me(arg, i)  # otherwise keep executing with incremented i
    print(arg)
call_me("I am calling me", 0)

Merge Sort

Copying halves of the array A

I assume we are now ready to get cracking. We have this unsorted array A as follows.

A = [4, 7, 20, 3, 9, 13, 5, 11]

As I mentioned earlier in a planning phase, we are going to copy arrays of left half(L) and right half(R) respectively.

def merge_sort(A):
    mid = len(A) // 2
    # copy slicing from the 0 to mid from array A
    L = A[:mid]
    # copy slicing from mid to the end from array A
    R = A[mid:]

We are going to recursively halve the arrays until it is not dividable. As I explained earlier we need a base case to stop recursion at some point, and it will be until the length of the array A becomes 1 since there is nothing to sort and the array is individable.

 def merge_sort(A):
    if len(A) > 1:
        ... previous code
        # recursively halve arrays
        merge_sort(L)
        merge_sort(R)

        # indices for array A, L, R 
        # for short term, i = j = k = 0 works as well.
        i = 0
        j = 0
        k = 0

As a result of the code above, arrays will look like this. Note that, each level of halving process happens simultaneously, so in this case, we took 4 steps to halve an array length of 8.

Merge and sort

Now, it is time to merge and sort back to an array A, to sort elements, we need to compare which one should come first. the first one would be the smaller ones, the larger one comes next. Implementation of the merge and sort will be like so, once an element is placed back in array A, index moves to a next element.

# while indices are within a range of array L and R
# note that indices i for L, j for R, k for A
while i < len(L) and j < len(R):
    if L[i] < R[j]:
        A[k] = L[i]
        i += 1
    else:
        A[k] = R[j]
        j += 1
    k += 1

There is the last thing left, that is to insert an element that hasn’t been moved to array A from L or R. This can happen when the length of L and R is different, in other words when the length of A is an odd number like 7.

... previous code
while i < len(L):
    A[k] = L[i]
    i += 1
    k += 1
while j < len(R):
    A[k] = R[j]
    j += 1
    k += 1

The process of the merge would look like this.

Time and Space Complexity Analysis

Time Complexity of Merge Sort

Seemingly, the time complexity of this algorithm O(n log n) because of divide and conquer phases (the halving arrays). But what about the merge and sort phases? It loops through each array to sort and merge, which is O(n). When worst-case exists, the other case doesn’t matter, so the time complexity is O(n).

Space Complexity of Merge Sort

How many memory spaces merge sort uses? A lot! it copies every half of the array and that means extra spaces, depending on the number of elements. Therefore space complexity of Merge Sort is O(n). In comparison to Insertion sort, it would be Merge sort O(n) > Insertion sort O(1).
It has been a long journey to the end, I hope you now have a good grasp of the concept.