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.