CITS2200 - Lecture 5

← Back to Home

CITS2200 - Lecture 4
Merge Sort - Slides

Lower Bound Complexity

• Lower bound complexity is the absolute minimum amount of time/resources an algorithm can take to solve a problem
  • Lowest time attainable with a perfectly efficient algorithm
  • Denoted with $\Omega$ instead of $O$

The lower bound for sorting non-natural/general numbers is:
$\Omega (n\log n)$

• @ You cannot make an algorithm faster than this

Merge-sort achieves this level of complexity

• Merge sort has complexity $O(n\log n)$ → $O$ used instead of $\Omega$ when describing the actual complexity of an algorithm

Quick note: Algorithms are typically shown sorting in ascending order, but it only requires a small change for any algorithm to sort in descending order

• ! In terms of increasing time: $O(n)<O(n\log n)<O(n^2)$

Divide-and-Conquer

Before we explore merge-sort:

• Divide-and-conquer is a general algorithm design paradigm
  • Paradigm → pattern or model

Divide-and-conquer is split into three parts:

1. Divide → divide input data $S$ into two disjoint subsets $S_1$ and $S_2$
   • Disjoint → no elements shared between sets
2. Recur → solve subproblems associated with $S_1$ and $S_2$
3. Conquer → combine solutions for $S_1$ and $S_2$ into solution for $S$

Merge-sort is based on the divide-and-conquer paradigm

Merge-Sort

Takes input sequence $S$ with $n$ elements:

1. Divide: partition $S$ into two sequences $S_1$ and $S_2$ of $\frac{n}{2}$ elements each
2. Recur: recursively sort $S_1$ and $S_2$
3. Conquer: merge $S_1$ and $S_2$ into a unique sorted sequence

Example of a Python merge and merge-sort algorithm:

def merge(S1, S2, S): # merge two sorted Python lists
    i = j = 0
    while i + j < len(S):
        if j == len(S2) or (i < len(S1) and S1[i] < S2[j]):
            S[i + j] = S1[i]   # copy ith element of S1
            i += 1
        else:
            S[i + j] = S2[j]   # copy jth element of S2
            j += 1
 
def merge_sort(S): #sort list using merge-sort algorithm
    n = len(S)
    if n < 2:
        return  # list is already sorted
 
    # divide
    mid = n // 2
    S1 = S[0:mid]   # first half
    S2 = S[mid:n]   # second half
 
    # conquer (recursion)
    merge_sort(S1)
    merge_sort(S2)
 
    # merge results
    merge(S1, S2, S)

Analysis of Merge-Sort:

• The height of the merge-sort tree is $O(\log n)$
  • Each split divides size by 2: $\frac{n}{2^k}=1\Rightarrow k={\log }_{2}n$
• Overall work done at the nodes of depth $i$ is $O(n)$
  • At depth $i$, there are $2^i$ subarrays of size $\frac{n}{2^i}$ → $2^i\times \frac{n}{2^i}=n$
• Thus, total run time of merge-sort is $O(n\log n)$

In algorithms, $\log n$ always means → ${\log }_{2}n$ which is the standard

---

CITS2200 - Lecture 6