Merge N sorted Array - merge sort from bottom-up implementation

July 21, 2016

   Merge N sorted arrays - C# practice



Time complexity analysis:

N sorted array, each array length is k, so the time complexity:

2k * N/2 + 4k * N/4 +... + 2^logN k * N/ (2^logN) = kN logN,

Today's research topic:
Coding is more of science, or just muscle memory, go for the intuition.

Review:
1. bottom-up implementation merge sort

2. Master Theorem - T(N) = 2T(N/2) + O(N)

3. Time complexity - come out kNlogN analysis

Read the article, and understand better about merge sort:

https://en.wikipedia.org/wiki/Merge_sort

Keywords:

Bitonic Mergesort
external merge sort - disk/ tape drives
external merge sort
merge sort
  - not inplace - must be allocated for the sorted output to be stored in
parallel mergesort
polyphase merge sort
natural merge sort - similar to a bottom up merge sort
stable sort,
TimSort,
tiled merge sort algorithm

Bottom-up implementation
Top-down implementation

comparison-based sorting algorithm

master theorem

average and worst-case performance

Lecture notes study:  (work on lecture notes, write down some interesting topic, do some research!)
http://algs4.cs.princeton.edu/lectures/22Mergesort.pdf

Actionable item:
Add study time 10 minutes for computer science, review theorems, lecture notes when writing a new blog.