Lab 01: Divide-and-Conquer Algorithms

In this practical, we will explore and implement three fundamental divide-and-conquer algorithms: Binary Search, Merge Sort, and Quick Sort. These algorithms are essential for efficient searching and sorting operations in computer science. They are widely used in various applications, from simple data retrieval to complex sorting tasks.

1. Binary Search

Binary Search is a divide-and-conquer algorithm used to efficiently locate a target element in a sorted array. By repeatedly halving the search interval, the algorithm significantly reduces the number of comparisons needed compared to linear search.

def binary_search(arr, target, low, high):
    if low > high:
        return -1  # Element not found
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, high)
    else:
        return binary_search(arr, target, low, mid - 1)

Complexity Analysis

• Best-case time complexity: $\Omega(1)$
  (if the target is found in the middle on the first try)
• Average-case time complexity: $\Theta(\log n)$
• Worst-case time complexity: $O(\log n)$
• Space Complexity:
  • $O(1)$ if implemented iteratively
  • $O(\log n)$ if implemented recursively (due to recursion stack)

2. Merge Sort

Merge Sort is a stable, divide-and-conquer sorting algorithm. It divides the input array into two halves, recursively sorts them, and then merges the two sorted halves back together. This algorithm is renowned for its predictable $\Theta(n \log n)$ time complexity in all cases.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)
 
def merge(left, right):
    sorted_arr = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_arr.append(left[i])
            i += 1
        else:
            sorted_arr.append(right[j])
            j += 1
    return sorted_arr + left[i:] + right[j:]

Complexity Analysis

• Time Complexity:
  • Best-case: $\Theta(n \log n)$
  • Average-case: $\Theta(n \log n)$
  • Worst-case: $\Theta(n \log n)$
• Space Complexity: $O(n)$
  (additional space is required for merging)

3. Quick Sort

Quick Sort is an in-place divide-and-conquer sorting algorithm that selects a pivot element, partitions the array into subarrays of elements less than and greater than the pivot, and then recursively sorts the partitions. Its efficiency greatly depends on the choice of pivot.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

Complexity Analysis

• Time Complexity:
  • Best-case: $\Theta(n \log n)$
    (balanced partitioning)
  • Average-case: $\Theta(n \log n)$
  • Worst-case: $O(n^2)$
    (when the pivot results in highly unbalanced partitions)
• Space Complexity:
  • Average-case: $\Theta(\log n)$ (due to recursion depth)
  • Worst-case: $O(n)$ (in the case of highly unbalanced recursion)

All Together

# 1. Binary Search
def binary_search(arr, target, low, high):
    if low > high:
        return -1  # Not found
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, high)
    else:
        return binary_search(arr, target, low, mid - 1)
 
# 2. Merge Sort
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)
 
def merge(left, right):
    sorted_arr = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_arr.append(left[i])
            i += 1
        else:
            sorted_arr.append(right[j])
            j += 1
    return sorted_arr + left[i:] + right[j:]
 
# 3. Quick Sort
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)
 
# Example usage
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("Merge Sort:", sorted_arr)
 
sorted_arr = quick_sort(arr)
print("Quick Sort:", sorted_arr)
 
index = binary_search(sorted_arr, 9, 0, len(sorted_arr) - 1)
print("Binary Search (9 found at index):", index)

Conclusion

Divide-and-conquer algorithms like Binary Search, Merge Sort, and Quick Sort form the backbone of efficient algorithm design. Binary Search provides rapid search capabilities in sorted arrays, Merge Sort guarantees stable and predictable performance, and Quick Sort, while generally efficient, requires careful pivot selection to avoid worst-case scenarios. Mastery of these techniques is essential for both theoretical understanding and practical application in computer science.

References

1. CS50x Week 3: Algorithms. (2025). Harvard University. Retrieved from https://cs50.harvard.edu/x/2025/weeks/3/ 

2. CS50’s Introduction to Programming with Python. (2022). Harvard University. Retrieved from https://cs50.harvard.edu/python/2022/ 

3. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C.
   Introduction to Algorithms, 3rd/4th Edition, MIT Press.