Contents
Definition
Merge sort yet another sorting algorithm that benefits from the divide-and-conquer principle. The main goal in this algorithm is to split the given array into individuals and merge them back during the course of the comparison.
Merge Sort seems kind of similar to the Merge sort, in the Comparison below you can study the differences and similarities. However, there is one challenge as I see in this algorithm is the merge. I find this part very complex, but besides its very easy to apprehend the algorithm.
Complexity Analysis
Time Complexity
- Best Case: O(n log n),
- Average Case: O(n log n),
- Worse Case: O(n log n)
Space Complexity
O(n)
Comparison to Quick Sort
In general terms, the Merge Sort is often compared to the Quick Sort. In some sense, they tend to act similarly as they inherit the same divide-and-conquer principle, to address a few of differences;
- Merge Sort demands a copy of the data structure, whereas Quick Sort applies the changes with no requirement of extra space allocated,
- Both of the algorithms split the given data structure. However, alternatively Merge Sort intends to split from the half to divide the left and right subsets into individual elements, whereas the Quick Sort picks a partition point and swaps the lower and greater values in the right and the left directions.
Operations
- The algorithm divides the array into half smaller chunks until the individual items left with by using recursion,
- once individuals created, they are compared and merged back from smaller to larger arrays
- Merge sort requires extra space allocation which makes it space complexity as O(n), whereas Quick Sort only keeps a space while swapping which makes its space complexity as O(log n). However the only similarity is that because of the recursive calls, the stack traces will be created upon each call that’s also considered as a space
Terms
- leftPointer: A pointer of the left/begin of the array
- rightPointer: A pointer of the right/endof the array
- middleElementPointer: Represents the element in the center of the array
- leftArray: The elements of the left side as a temporary storage
- rightArray: The elements of the rıght side as a temporary storage
Code
You can checkout my GitHub repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/SortingAlgorithms