README.md

MergeSort Implementations

In this repo I tried my best to implement the MergeSort in various ways:

• sequentailly
• via Threads (parallel):
  • optimized Implementation
  • Naive Implementation (had to take it down it was a bit buggy!).
• via WorkStealingThreadPool
• via ForkJoin

---

Papers/Books I've read:

A) BOOK What's New in java 8 to read it please refer here.

B) In order to maximize the understanding of mergesort and it's implementations i've read your pdfs and the following papers from open-scources:

• Knowing and understanding the differance between Executor, Executors and ExecutorService.

• Reading the complete javaDoc of the following:

  • ThreadPoolExecutor, Fork/Join, RecursiveAction.

• Tried my best to understand the concept of Amdahl's law.

• Parallel Programming from Zuric lst.ethz.ch.

• Distributed Algorithms and Optimization (stanford) (partially read) from Drawbacks of Divide and Conquer.

• Performance analysis of multithreaded sorting algorithms by Kevin Jouper, Henrik Nordin (amazing/read just the mergesort parts till now.)

C) In order to optimize the code I did read the following:

• Writing Testable Code.

• chosing the rigt method to generate random data thus its being used in all test cases:

  • Math.random() versus Random.nextInt(int) .
  • Random Number Generation (Oracle fourm).
  • Random Number Generator in Java. chosing the ThreadLocalRandom or SecureRandom is a bit overkill for our program.
  • having very little understanding of the Diehard tests.

• premature optimization >>>1 vs /

  • wikipedia premature optimization
  • Is shifting bits faster than multiplying and dividing in Java?
  • Should I bit-shift to divide by 2 in Java?

---

Problems encountered me through the Coding per exercise:

Exercise 2: (Contains unreviewed Issue)

• I could NOT understand the logic behind terminating the threads via a boolean flag and synchronized method!.
• understanding the Amdahl's law.
• I learned that lambdas are not to be treated as Anonymous classes thus according to the book What's New in java 8 :

  A lambda expression is not an anonymous class; it actually uses invokedynamic in the byte-code.

Exercise 3:

• the trouble i went throught could be observed in this StackOverFlow Question (asked and answered by me).

• Choosing the right Threadpool that will alow the program to work freely without having any memory issues when sorting big data such like 1000.000 .

  • newCachedThreadPool worked till some amount of data i think 70000then melt down happend.
  • newFixedThreadPool failed miserably thus the program would be in hold whenever the threads are busy.
  • newWorkStealingPoolworked like a charm due to the fact that the workStealing according to the javaDoc:

    "creates a work-stealing thread pool using all available processors as its target parallelism level."

• managing the Sorting without wasting objects by making the `sort(LinkedList data) static.

Exercise 4:

• was in general not hard to implement and as in the pervious exercise i had to make the `sort(LinkedList data) method static.

---

Time Analysis here

---