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
                Middle = length of Array / 2
                LeftArray = left half of Array
                RightArray = right half of Array
                RETURN Merge(MergeSort(LeftArray), MergeSort(RightArray))
      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
                          move first item of RightArray to SortedArray
                     IF there are still items in LeftArray THEN
                          move all to SortedArray
                          move all items in RightArray to SortedArray
           RETURN SortedArray

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.