# Merge Sort

Link to code page: https://github.com/sefx5ever/SCU_DSA/blob/master/HW2/merge_sort_06170171.py

### Flow Desription:
1. Find the middle point to divide the array into two half
2. Call mergeSort for first half
3. Call mergeSort for second half
4. Merge the two halves sorted in step 2 and 3
5. Repeat Step

### Difficulties:
1. Same mistakes I made in the heap sort, I was the easiest to error in recursive and OOP, so start to learn those thing in the online courses to boost up my coding skill.
2. This is the most hardest sort to code when I try to turn concept into code, I was stuck almost 6 hours, I watched a lot of tutorial video and psuduo code, but I failed eventually, I just code the module which is not functionable.

### Test:

### Extra Description:
* #### Complexity
| Data Structure | Time Complexity[Average] | Time Complexity[Worst] |
| ------------- | ------------- | ------------- |
| Merge Sort | O(n log(n)) | O(n log(n)) |

* #### Important Characteristics of Merge Sort:
* Merge Sort is useful for sorting linked lists.
* Merge Sort is a stable sort which means that the same element in an array maintain their original positions with respect to each other.
* The space complexity of Merge sort is O(n). This means that this algorithm takes a lot of space and may slower down operations for the last data sets.

* #### Merge Sort is a divide and conquer algorithm. It works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem. So Merge Sort first divides the array into equal halves and then combines them in a sorted manner.

### References:
* https://www.youtube.com/watch?v=TzeBrDU-JaY
* https://www.youtube.com/watch?v=6pV2IF0fgKY&t=141s
* https://www.youtube.com/watch?v=mB5HXBb_HY8&t=448s
* https://www.youtube.com/watch?v=ak-pz7tS5DE&t=26s
* https://www.youtube.com/watch?v=alJswNJ4P3U
* https://www.youtube.com/watch?v=2DmK_H7IdTo&t=4s
* https://medium.com/karuna-sehgal/a-simplified-explanation-of-merge-sort-77089fe03bb2