Merge Sort Algorithm Overview

Sorting in N-Log-N And Linear Time

• Sorting problem: Given an unordered data set, arrange elements in non-decreasing order.

Merge Sort

• Divide and Conquer Pattern: break down a problem into a smaller problem, solve the smaller problems recursively, and combine the solutions.
• Algorithm:
  • Divide: if the input has 1 or fewer elements, it is already sorted. Otherwise, split the input into two halves.
  • Conquer: recursively sort the two halves.
  • Combine: merge the two sorted halves into a single sorted sequence.
• Performance:
  • Time Complexity: O(n log n)
  • Space Complexity: O(n) due to the extra space needed for the merging process.

Merge Sort Illustration

• The merge sort process can be visualized as a binary tree.
  • Each node represents a recursive call, storing both the unsorted sequence before processing and the sorted sequence after.
  • The root node represents the initial call to the sorting algorithm.
  • Leaf nodes represent calls on subsequences of size 0 or 1, meaning they are already sorted.
• The height of the merge sort tree is O(log n), as each recursive call divides the sequence in half.

Quick Sort

• Algorithm:
  • Divide:
    • If input has 1 or fewer elements, it is already sorted. Otherwise, select a pivot element (often the last element in the sequence).
    • Partition the input into:
      • L (elements smaller than the pivot)
      • E (elements equal to the pivot)
      • G (elements greater than the pivot)
  • Conquer: Recursively sort L and G.
  • Combine: Join L, E, and G together.
• Tree Visualization:Similar to merge sort, quick sort can be visualized as a binary tree with a similar interpretation of nodes and their meaning.
• Performance:
  • Worst-Case Time Complexity: O(n^2)
  • Best-Case Time Complexity: O(n log n)
  • Average Time Complexity: O(n log n)
  • Space Complexity: O(log n) on average due to the recursive call stack.

Quick Sort Illustration

• The pivot element is chosen (often the last element), and the sequence is partitioned around this pivot.
• The process recurses through the partitions until base cases are reached, and the sorted sub-sequences are joined back together.

Bucket Sort

• A linear time sorting algorithm, which implies its performance is directly proportional to the number of elements to be sorted.
• Suitable for data that is evenly distributed within a known range.
• Algorithm:
  • Create a number of buckets equal to the range of the input data.
  • For each element in the input:
    • Calculate its bucket index based on its value.
    • Insert the element into the corresponding bucket.
  • Sort the elements within each bucket (using other sorting algorithms).
  • Concatenate the sorted buckets to produce the final sorted sequence.

Radix Sort

• Also a non-comparison based sorting algorithm, which can achieve linear time complexity in certain cases.
• Algorithm:
  • Sort the input sequence digit by digit, starting from the least significant digit.
  • For each digit position:
    • Create buckets for each possible digit value (0-9).
    • Distribute input elements into buckets based on their digit value in that position.
    • Concatenate the buckets to form the sorted sequence for this digit position.
    • Use the output of the previous stage as input for the next digit position.

Heap Sort

• Will be covered in future lectures on heaps.