================================================================================
         DATA STRUCTURES AND ALGORITHMS
         HOMEWORK 10: Advanced Sorting & Searching
         State University of Zanzibar (SUZA)
================================================================================

SUBMISSION REQUIREMENTS:
- Submit .c source code file(s) AND handwritten work (scanned/photographed)
- Code must compile and run without errors
- Include your Name, Registration Number, and Date at the top of each file
- VIVA REQUIRED: You must demonstrate and explain your code in person

INTEGRITY DECLARATION:
"I declare that this work is my own. I understand that submitting
AI-generated code or copied work will result in zero marks and
disciplinary action."

Signature: ________________  Date: ________________

================================================================================
PROBLEM 1: Merge Sort (25 marks)
================================================================================

Implement Merge Sort with detailed output:

   void mergeSort(int arr[], int left, int right);
   void merge(int arr[], int left, int mid, int right);

Requirements:
a) Print each split and merge step:
   Splitting: [38, 27, 43, 3, 9, 82, 10]
   Left half: [38, 27, 43]  Right half: [3, 9, 82, 10]
   ...
   Merging: [27, 38] + [3, 43] -> [3, 27, 38, 43]
   ...

b) Count total comparisons made during merge operations.

c) [HANDWRITTEN] Draw the complete recursion tree for mergeSort on
   [38, 27, 43, 3, 9, 82, 10]. Show the array at each level of
   splitting and merging.

d) What is the time complexity? Why is it O(n log n) in ALL cases?
   [HANDWRITTEN answer]

================================================================================
PROBLEM 2: Quick Sort (25 marks)
================================================================================

Implement Quick Sort using last element as pivot:

   void quickSort(int arr[], int low, int high);
   int partition(int arr[], int low, int high);

Requirements:
a) Print pivot selection and partition result at each step:
   Array: [10, 7, 8, 9, 1, 5]
   Pivot: 5
   After partition: [1, 5, 8, 9, 10, 7], pivot at index 1
   ...

b) [HANDWRITTEN] Trace the partition function on [10, 7, 8, 9, 1, 5]:
   Show the value of i and j at each step.
   Show each swap performed.
   Show the final position of the pivot.

c) Test on already sorted array [1, 2, 3, 4, 5, 6, 7].
   How many comparisons are made? Why is this the worst case?

d) [HANDWRITTEN] What happens if you always pick the first element as pivot
   on sorted data? Draw the recursion tree to show why it's O(n^2).

================================================================================
PROBLEM 3: Binary Search (25 marks)
================================================================================

Implement both iterative and recursive binary search:

   int binarySearchIterative(int arr[], int n, int key);
   int binarySearchRecursive(int arr[], int low, int high, int key);

Requirements:
a) For each search, print the steps:
   Searching for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
   Step 1: low=0, high=9, mid=4, arr[4]=16 < 23, go right
   Step 2: low=5, high=9, mid=7, arr[7]=56 > 23, go left
   Step 3: low=5, high=6, mid=5, arr[5]=23 == 23, FOUND at index 5

b) Search for these values and record comparisons for each:
   - 23 (found)
   - 91 (found, last element)
   - 2 (found, first element)
   - 50 (not found)

c) [HANDWRITTEN] For the array above, draw the binary search decision tree.
   Each internal node shows the comparison, leaves show the result.

d) What is the maximum number of comparisons for an array of size n?
   For n=1000? For n=1,000,000?

================================================================================
PROBLEM 4: Search in Rotated Sorted Array (25 marks)
================================================================================

A sorted array has been rotated at some pivot unknown to you.
Example: [0,1,2,4,5,6,7] rotated at index 3 -> [4,5,6,7,0,1,2]

Implement:
   int searchRotated(int arr[], int n, int key);

Requirements:
a) Use modified binary search (O(log n), not O(n)).

b) [HANDWRITTEN] Explain the algorithm:
   - How do you determine which half is sorted?
   - How do you decide which half to search?

c) Test cases:
   arr = [4, 5, 6, 7, 0, 1, 2]
   - Search 0 -> index 4
   - Search 3 -> -1 (not found)
   - Search 6 -> index 2

d) [HANDWRITTEN] Trace searchRotated([4,5,6,7,0,1,2], 7, 0):
   Show low, high, mid at each step and the decision made.

================================================================================
VIVA QUESTIONS (be prepared to answer):
================================================================================
1. What is the time complexity of Merge Sort vs Quick Sort? Best and worst cases?
2. Explain the partition process in Quick Sort step by step.
3. Why is Quick Sort generally faster than Merge Sort in practice?
4. What is the space complexity of Merge Sort? Why?
5. Can binary search work on unsorted arrays? Why not?
6. Derive the time complexity O(log n) for binary search.
7. Modify your binary search to find the first occurrence of a duplicate value.

================================================================================
GRADING RUBRIC:
   Problem 1 (Merge Sort):     25 marks
   Problem 2 (Quick Sort):     25 marks
   Problem 3 (Binary Search):  25 marks
   Problem 4 (Rotated Search): 25 marks
   Viva Demonstration:         Required (multiplier: 0 or 1)
   Late Penalty: -10% per day
================================================================================