Merge Sort

How to analyze the time complexity for Merge Sort?

  • This video helps a lot:
  • Prereq: how to understand O(n), O(logn) etc.
    • say the input size is n, then for a loop that starts from 0 and iterates until n or n-1, we say the time complexity for such a loop is O(n)
      • this is also why, we say the time complexity for binary search is O(logn)
        • i.e. in binary search, we only need to search logn times before we find the target because each time, we cut the size of the input by half, e.g. with an input of size 16, we only need to cut 4 times or less before we could find the target, thus, it’s log16 = 4
      • this is also why, we say the time complexity for insertion sort is O(n2)
        • i.e. insertion sort has two for loops, each for loop has to iterate n times, thus, in total, it will have to loop through n*n, i.e. O(n2) time complexity
  • Then based on the code below, merge sort time complexity could be analyzed as below:
    • we use T(n) to denote the total running time for merge sort to work on an array of size n
    • then sort(arr, l, m) takes T(n/2) time since it’s the half size of the original size
    • similarly, sort(arr, m+1, r) also takes T(n/2) time
    • but merge(arr, l, m, r) will take c*n time (c as a constant) since we’ll have to go through the entire array
    • then T(n) could be represented as T(n) = 2*T(n/2) + c*n (function 1)
    • apparently, this is a recursive function, from it, we could get the following:
      • T(n/2) = 2*T(n/4) + c*n
      • T(n/4) = 2*T(n/8) + c*n
      • T(n/8) = 2*T(n/16) + c*n
      • …..
      • take those into the function 1 and simplify it, we could get: T(n) = 2kT(n/2k)+ k*c*n (function 2)
      • we want to deduce this to T(1) because that is what we know: constant time.
      • in that case, n/2k will be equal to 1 , then we could get n = 2k, then we use log on both sides of the equation, we could get logn = log2k = k (function 3)
      • we take function 3 into function 2, we could get T(n) = 2lognT(1)+ logn*c*n, then using Big O notation (lower-order and constant operations could be neglected), this could be represented as T(n) = O(logn*n) = O(n*logn), i.e. the so-called O(nlogn) time complexity for MergeSort.

Merge Sort is a stable sorting algorithm: the order of equal keys in the original input is respected.

Merge Sort is NOT an in-place algorithm: the amount of extra space needed for merge sort is proportional to the size of the input array, this is different from other sorting algorithms like insertion sort or bubble sort which requires only a temp variable to do swap. However, in merge sort, we divide the arrays into two sub-arrays and we make copy of the entire two sub-arrays. Thus, the extra memory required for doing merge sort is proportional to the size of the input array. We say the space complexity of merge sort is O(n) which means its extra memory required is proportional to the size of the input array.

Merge sort works like this:

It partitions the original array into the most atomic elements, then compare and combine them, thus the code looks like the following:

public static void main(String... args){

int[] a = new int[]{4,3,9,8,7};

MergeSort test = new MergeSort();
test.sort(a, 0, a.length-1);


public void sort(int[] arr, int l, int r){
if(l < r){
int m = (l+r)/2;
sort(arr, l, m);
sort(arr, m+1, r);
merge(arr, l, m, r);

private void merge(int[] arr, int l, int m, int r) {
//find sizes of two subarrays that are to be merged
int size1 = m-l+1;
int size2 = r-m;

//copy the two subarrays into two temp arrays
int[] tempL = new int[size1];
int[] tempR = new int[size2];
for(int i = 0; i < size1; i++){
tempL[i] = arr[l+i];
for(int i = 0; i < size2; i++){
tempR[i] = arr[m+i+1];

//now we merge the two subarrays

//initial indices of the two subarrays
int i = 0, j = 0;

//initial index of the merged subarray array
int k = l;

while(i < size1 && j < size2){
if(tempL[i] <= tempR[j]){
arr[k] = tempL[i];
} else {
arr[k] = tempR[j];

//copy remaining list into arr if any
while(i < size1){
arr[k++] = tempL[i++];
while(j < size2){
arr[k++] = tempR[j++];

A sample walkthrough of the code (omitted merge() function), recursion is so cool/powerful!



Insertion Sort

The idea of insertion sort is to keep inserting the remaining elements one by one into the previously sorted part until no remaining elements.

Based on the description on wikipedia, I implemented insertion sort completely by myself and ran several test cases:

public int[] insertionSort(int[] nums){
for(int i = 1; i < nums.length; i++){
int j = i-1;
if(nums[i] > nums[j]) continue;
while(j >= 0 && nums[j] > nums[i]){
swap(nums, j, i);
return nums;

private void swap(int[] nums, int j, int i) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;


I came up with a new way of writing insertion sort today (6/27/2016), completely by myself, although others might have written this way many times already, still feeling excited about it:

public int[] insertionSortAgain(int[] nums){
for(int i = 1; i < nums.length; i++){
for(int j = i-1; j >= 0; j--){
if(nums[j+1] <= nums[j]){
int temp = nums[j+1];
nums[j+1] = nums[j];
nums[j] = temp;
return nums;

The key is to use and j+1 in the inner for loop, instead of using i, otherwise, things won’t work!

Http vs. HttpS

Marked this one as one of my favorite questions:


What are benefits of using HTTPS over HTTP?
HTTPS means that you tunnel the HTTP protocol over TLS/SSL which encrypts the HTTP payload. So the benefit is that HTTP requests and responses are transmitted securely over the wire, e.g. your Internet Service Provider does not know what you’re doing.

How to use HTTPS?
Enable it at your endpoint, in general a web server in front of your application server. Most web servers (e.g. IIS, Apache) support this by configuration. Depending on your confidentiality requirements this may not be enough.
Can we use HTTPS for only login purpose and then onwords HTTP?
Technically this is possible, but it introduces some security risks. Example: After a secured login you transmit session IDs identifying the user. If you transmit those session IDs unsecurely (no SSL), session hijacking becomes a risk (‘man-in-the-middle’)

Is processing time required for HTTPS is greater than HTTP?
Yes, key negotiation (handshaking) requires a lot CPU capacity.

Garbage Collection

  • GC is a mechanism provided by JVM to reclaim heap space from objects
  • When does an object become eligible for garbage collection?
    • If it’s not reachable by any live threads or any static references, or you could say, when all of its references become null.
    • Cyclic dependencies do not count which means that it’s also eligible for GC. e.g. Object A has reference to Object B and Object B also references Object A, and they don’t have any live thread references, then both Object A and B are eligible for GC.
  • This is a pretty handy and quick description about how GC works in Java: