Leetcode 23: Merge K Sorted Lists

July 19, 2016

 Problem statement:

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
 Julia's first two practices in 2015:
1. Naive solution:
https://github.com/jianminchen/Leetcode_C-/blob/master/MergeKSortedLists_A_No23.cs


2. Implementation using merge sort: August 12, 2015
https://github.com/jianminchen/Leetcode_C-/blob/master/MargeKSortedLists_B_No23.cs

Come back to work on this problem in 2016, July 19:

Study those blogs:
1. Most favorite one:
http://bangbingsyb.blogspot.ca/2014/11/leetcode-merge-k-sorted-lists.html

Specially, the third discussion using divide and conquer, the conclusion that the merge solution is same time efficiency using heap solution Nklog(k), k is the number of arrays, and N is the length of the array, assuming that each array has same length.

1. http://www.cnblogs.com/TenosDoIt/p/3673188.html

2. http://bangbingsyb.blogspot.ca/2014/11/leetcode-merge-k-sorted-lists.html

3. http://codeganker.blogspot.ca/2014/08/leetcode_26.html

4. http://www.cnblogs.com/springfor/p/3869217.html

5. https://github.com/shawnfan/LintCode/blob/master/Java/Merge%20k%20Sorted%20Arrays.java

7. Excellent article - Julia, share your personal story as well.
http://codeganker.blogspot.ca/2014/08/leetcode_26.html

Read the article: 

http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/04MergeQuick.pdf

Julia's question and answer: 
1. Ideas to improve practice?
Answer:
  Ideas to construct the practice:
   1. Need to work on blog 7 - 3 solutions using C#, apply to "merge k sorted array".

Learn bottom-up merge sort, and know the time complexity as well.

C# solution - merge k sorted array - using bottom-up implementation merge sort
https://gist.github.com/jianminchen/d5fab2036647d380f20c908e91a81132

   2. Write down the proof of "divide and conquer" time complexity comparison using heap, O(nk logk)
       Show some simple example to help understand the time complexity.
   3. Warm up the code practice a few times, aiming to write 20 minutes for a solution
   4. Need to figure out master theorem quickly.

2. Can you work on a small example to illustrate some analysis?
Copy the image from Princeton's lecture note:

3. Can you write some C# code this time to make your own mark?

Actionable items:

Read the article, and write down questions - prepare a further reading list. (30 minutes reading )
https://en.wikipedia.org/wiki/Merge_sort
Notes:

keywords:  (remember 14 keywords)
average and worst-case performance
Bitonic Mergesort
Bottom-up implementation
comparison-based sorting algorithm
external merge sort - disk/ tape drives

external merge sort
master theorem
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
Top-down implementation

Variants:
  1. reducing the space complexity
  2. cost of copying

locality of reference

memory hierarchies
cache-aware version of merge sort algorithm
tiled merge sort algorithm

Parallel merge sort

Merge sort parallelizes well due to use of the divide-and-conquer method.

-
Comparison with other sort algorithms

heapsort   vs merge sort

O(1) auxiliary space instead of merge sort's O(n).

efficient quicksot implementations generally outperform mergesort for sorting RAM-based arrays - ?

merge sort is a stable sort and is more efficient at handling slow-to-access sequential media.

Merge sort is often the best choice for sorting a linked list.

the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others(such as heapsort) completely impossible.

Java, Array.sort() methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficicency switch to insertion sort when fewer than seven array elements are being sorted.

Python uses Timsort, another tuned hybrid of merge sort and insertion sort.

--
More reading:
30 minutes to review:
http://algs4.cs.princeton.edu/lectures/22Mergesort.pdf


5 minutes reading:
http://infolab.stanford.edu/~ullman/fcscnotes/notes9.pdf

20 minutes reading - plan to read - parallel merge sort
http://stanford.edu/~rezab/dao/notes/Lecture04/cme323_lec4.pdf

Read 10 minutes a time - get lost and enjoy reading ...


http://web.archive.org/web/20150120063131/https://android.googlesource.com/platform/libcore/+/jb-mr2-release/luni/src/main/java/java/util/TimSort.java

Will come back very soon.