# Merge Sort

Understanding Merge Sort

• Merge Sort is a type of sorting algorithm that employs a divide-and-conquer 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 divide-and-conquer 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 trade-off is its relatively high memory requirement, which might not make it suitable for systems with limited memory.