Merge Sort
Understanding Merge Sort
 Merge Sort is a type of sorting algorithm that employs a divideandconquer strategy.
 It continuously divides an unsorted list into smaller subsets until each subset contains only one element.
 Once the subsets consist of a single element, merge sort combines these subsets in a particular order to produce the sorted list.
How Merge Sort Works
 Merge Sort begins by dividing the unsorted list into N subsets, each containing one element (a list containing one element is considered sorted).
 Subsequently, it repeatedly merges these subsets to produce new sorted subsets until there is only one subset left.
 This remaining subset is the sorted list.
Implementing Merge Sort
 Merge Sort can be implemented recursively due to its divideandconquer nature.
 The key process in the Merge Sort is the merge process, which takes two smaller sorted lists and combines them together into a single, sorted, new list.
Example of Merge Sort

A simplified pseudocode representation for merge sort:
FUNCTION MergeSort(Array) IF length of Array <= 1 THEN RETURN Array ELSE Middle = length of Array / 2 LeftArray = left half of Array RightArray = right half of Array RETURN Merge(MergeSort(LeftArray), MergeSort(RightArray)) ENDIF END FUNCTION FUNCTION Merge(LeftArray, RightArray) Create Empty List, SortedArray WHILE there are items in either LeftArray or RightArray DO IF (there are still items in both arrays) THEN IF first item of LeftArray < first item of RightArray THEN move it to SortedArray ELSE move first item of RightArray to SortedArray ENDIF ELSE IF there are still items in LeftArray THEN move all to SortedArray ELSE move all items in RightArray to SortedArray ENDIF ENDIF ENDWHILE RETURN SortedArray END FUNCTION
Evaluating Merge Sort
 Merge Sort is very effective as it consistently performs at O(n log n), regardless of the input data.
 It creates an excellent choice for large datasets that need to be sorted.
 However, it has a space complexity of O(n) because it requires additional space for the temporary arrays during the merging process.
 Despite its efficiency in sorting, Merge Sort would not be ideal in situations where memory space is constrained.
Understanding Space Complexity
 Space Complexity refers to the total amount of memory space that an algorithm needs to execute.
 O(n) space complexity means as the input data increases linearly, the space required by the algorithm also increases linearly.
 While Merge Sort is efficient in time, the tradeoff is its relatively high memory requirement, which might not make it suitable for systems with limited memory.