DAY 10 : Sorting & Searching Using Recursion in Java | My DSA Journey (Recursion)

---

Introduction

Welcome to Day 10 of my DSA Journey!
For the past few days, I’ve been focusing on one of the most fundamental and important concepts in DSA — Recursion.

Solved some medium level questions on recursion and also learn some sorting algorithm using recursion which helps me to grasp the concept how recursion is working behind the scenes.

I’m documenting my journey in public to stay consistent and to help others who are also learning DSA from scratch.

Here’s what I learnt in last 3 days:

Day 7:
→ Recursive Linear Search
→ Recursive Binary Search
→ Search in Rotated Sorted Array

Day 8:
→ Recursive Bubble Sort
→ Recursive Selection Sort

Day 9:
→ Merge Sort
-> Quick Sort

Let’s break down each of these topics below 👇

---

Q 1. Recursive Linear Search:

Given an array and a target element, I need to search for the element recursively (without using loops).
If the target is found, return its index; otherwise, return -1.

Approach:

Instead of using a loop to iterate through the array (like in iterative linear search), I used recursion to go element by element:

• Base Case
  If the index is out of bounds (i.e., index == array.length), return -1 — this means the element is not found.

• Check Condition
  If the current element matches the target, return the current index.

• Recursive Step
  Otherwise, call the function again with the next index (index + 1).

Example:

Input: arr = [3, 8, 5, 2, 9], target = 2

Steps:

→ arr[0] = 3 ❌
→ arr[1] = 8 ❌
→ arr[2] = 5 ❌
→ arr[3] = 2 ✅ (target found)

Output: 3

Code:

static int search(int[] arr, int target, int index) {
    if (index == arr.length) {
        return -1;
    }

    if (arr[index] == target) {
        return index;
    }

    return search(arr, target, index + 1);
}

---

Q 2. Recursive Binary Search:

Given a sorted array, implement a recursive function to search for a target value. Return the index if found, else return -1.

• Input: A sorted array and a target value.
• Task: Use the binary search algorithm recursively to find the target.
• Output: Index of target if present, else -1.

What is Binary Search?

Binary Search is a highly efficient searching algorithm used to find an element in a sorted array by repeatedly dividing the search interval in half.

• Time Complexity: O(log n)
• Only works on sorted data
• It uses the Divide and Conquer strategy

Approach:

Binary Search follows the Divide and Conquer method:

1. Find the middle element.
2. If mid == target, return mid.
3. If target < mid, search the left half.
4. If target > mid, search the right half.
5. Repeat the process recursively with updated start and end.

Example:

Input: arr = [2, 4, 7, 10, 15, 18], target = 10

Steps:

→ start = 0, end = 5
→ mid = (0 + 5) / 2 = 2 → arr[2] = 7 ❌
→ target > 7 → search in right half → start = 3, end = 5
→ mid = (3 + 5) / 2 = 4 → arr[4] = 15 ❌
→ target < 15 → search in left half → start = 3, end = 3
→ mid = 3 → arr[3] = 10 ✅ (target found)

Code:

static int binarySearch(int[] arr, int target, int start, int end) {
    if (start > end) {
        return -1;
    }

    int mid = start + (end - start) / 2;

    if (arr[mid] == target) {
        return mid;
    }

    if (target < arr[mid]) {
        return binarySearch(arr, target, start, mid - 1);
    }

    return binarySearch(arr, target, mid + 1, end);
}

---

Q 3. Search in Rotated Sorted Array:

Given a rotated sorted array, find the index of the target element. If the element is not present, return -1.

A rotated sorted array is a sorted array that has been rotated at some pivot.
For example: [4, 5, 6, 7, 0, 1, 2] is a rotation of [0, 1, 2, 4, 5, 6, 7].

Approach:

This is a variation of binary search that accounts for the rotation.

1. Find the mid index.
2. Check if arr[mid] == target, return mid.
3. Determine if the left half is sorted:
   • If arr[start] <= arr[mid], then:
     • If target lies in the left half → search left
     • Else → search right
4. Else the right half is sorted:
   • If target lies in the right half → search right
   • Else → search left

This logic is applied recursively.

Example:

Input: arr = [4, 5, 6, 7, 0, 1, 2], target = 0

Steps:

• mid = 3 → arr[3] = 7
• Left side [4, 5, 6, 7] is sorted
• Target 0 is not in [4, 5, 6, 7] → go right

Now:

• new start = 4, end = 6
• mid = 5 → arr[5] = 1
• Right side [1, 2] is sorted
• Target 0 is less than 1 → go left

Now:

• start = 4, end = 4 → arr[4] = 0 ✅ found!

Code:

static int search(int[] arr, int key, int start, int end) {
    if (start > end) {
        return -1;
    }

    int mid = start + (end - start) / 2;

    if (arr[mid] == key) {
        return mid;
    }

    // Left half is sorted
    if (arr[start] <= arr[mid]) {
        if (key >= arr[start] && key <= arr[mid]) {
            return search(arr, key, start, mid - 1);
        } else {
            return search(arr, key, mid + 1, end);
        }
    }

    // Right half is sorted
    if (key >= arr[mid] && key <= arr[end]) {
        return search(arr, key, mid + 1, end);
    }

    return search(arr, key, start, mid - 1);
}

---

Q 4. Recursive Bubble Sort:

Given an unsorted array, and our goal is to sort it using the Bubble Sort algorithm — but using recursion instead of loops.

What is Bubble Sort?

Bubble Sort is a simple comparison-based sorting algorithm.
It works by repeatedly swapping adjacent elements if they’re in the wrong order.
After each full pass, the largest element "bubbles up" to its correct position.

Time Complexity:

• Worst/Average: O(n²)
• Best (already sorted): O(n)

Approach:

We use two recursive parameters:

• r: represents the remaining passes (outer loop).
• c: represents the current index in the pass (inner loop).

Initially, r = arr.length - 1 & c = 0

Steps:

1. If r == 0, the array is sorted → base case.
2. If c < r:
   • Compare arr[c] and arr[c+1].
   • If arr[c] > arr[c+1], swap them.
   • Call bubble(arr, r, c+1) to continue the pass.
3. If c == r, one pass is complete → call bubble(arr, r-1, 0) for the next pass.

Example:

Input: arr = [4, 3, 2, 1];

Steps:

First Pass (r = 3):

• Compare 4 and 3 → swap → [3, 4, 2, 1]
• Compare 4 and 2 → swap → [3, 2, 4, 1]
• Compare 4 and 1 → swap → [3, 2, 1, 4]

Second Pass (r = 2):

• Compare 3 and 2 → swap → [2, 3, 1, 4]
• Compare 3 and 1 → swap → [2, 1, 3, 4]

Third Pass (r = 1):

• Compare 2 and 1 → swap → [1, 2, 3, 4]

✅ Final Sorted Array: [1, 2, 3, 4]

Code:

public static void main(String[] args) {
    int[] arr = {4, 3, 2, 1};
    bubble(arr, arr.length - 1, 0);
    System.out.println(Arrays.toString(arr));
}

static void bubble(int[] arr, int r, int c) {
    if (r == 0) {
        return;
    }
    if (c < r) {
        if (arr[c] > arr[c + 1]) {
            // Swap
            int temp = arr[c];
            arr[c] = arr[c + 1];
            arr[c + 1] = temp;
        }
        bubble(arr, r, c + 1);
    } else {
        bubble(arr, r - 1, 0);
    }
}

---

Q 5. Recursive Selection Sort:

Given an unsorted array, our goal is to sort it using the Selection Sort algorithm — but implemented using recursion instead of loops.

What is Selection Sort?

Selection Sort is a simple comparison-based sorting algorithm.
In each pass, it selects the maximum (or minimum) element from the unsorted part of the array and places it at its correct position.

• After each pass, the largest unsorted element is placed at the end of the remaining array.

Time Complexity:

• Worst / Average / Best: O(n²)

Approach:

We simulate the two nested loops of selection sort using recursion:

• r → remaining number of passes (like the outer loop).
• c → current index (like the inner loop).
• max → index of the maximum element found so far.

Steps:

1. Base Case: If r == 0, array is fully sorted.
2. Inner Recursive Case (c < r):
   • Compare arr[c] with arr[max].
   • If arr[c] > arr[max], update max = c.
   • Recur with selection(arr, r, c+1, max).
   • else, max will not updated.
   • Recur with selection(arr, r, c+1, max).
3. Outer Recursive Case (c == r):
   • Swap the max element with the last unsorted element (arr[r-1]).
   • Recur for the remaining part: selection(arr, r-1, 0, 0).

Example:

Input: arr = [4, 3, 2, 1]

Steps:

First Pass (r = 4):
Find max from index 0 to 3 → max = 0 → swap with arr[3]
→ [1, 3, 2, 4]

Second Pass (r = 3):
Find max from index 0 to 2 → max = 1 → swap with arr[2]
→ [1, 2, 3, 4]

Third Pass (r = 2):
Find max from index 0 to 1 → max = 1 → swap with arr[1]
→ [1, 2, 3, 4]

Fourth Pass (r = 1):
Only one element left → already sorted ✅

Final Sorted Array: [1, 2, 3, 4]

Code:

public static void main(String[] args) {
    int[] arr = {4, 3, 2, 1};
    selection(arr, arr.length, 0, 0);
    System.out.println(Arrays.toString(arr));
}

static void selection(int[] arr, int r, int c, int max) {
    if (r == 0) {
        return;
    }
    if (c < r) {
        if (arr[c] > arr[max]) {
            selection(arr, r, c + 1, c);
        } else {
            selection(arr, r, c + 1, max);
        }
    } else {
        // Swap max with last element of unsorted part
        int temp = arr[max];
        arr[max] = arr[r - 1];
        arr[r - 1] = temp;

        // Recur for remaining array
        selection(arr, r - 1, 0, 0);
    }
}

---

Q 6. Merge Sort:

Given an unsorted array, our goal is to sort it using the Merge Sort algorithm.

What is Merge Sort?

Merge Sort is a classic divide-and-conquer algorithm that breaks the array into smaller subarrays, sorts them recursively, and then merges them.

Merge Sort divides the array into two halves, recursively sorts both halves, and then merges the sorted halves to produce the final sorted array.

It is stable, efficient, and performs well even for large datasets.

Time Complexity:

• Best, Average, Worst: O(n log n)
  Space Complexity: O(n) (because of the temporary array used during merging)

Approach:

We use two functions:

1. mergeSort(arr, low, high):

   • Recursively divides the array into two halves until a single element is left.
   • Finds the middle index using mid = (low + high) / 2
   • Recursively calls itself on the left half and right half.
   • Finally, calls merge2() to merge the two sorted halves.

2. merge(arr, low, mid, high):

   • Merges two sorted subarrays: from low to mid and mid+1 to high.
   • Creates a temporary array to hold the merged result.
   • Uses two pointers (left and right) to compare and merge elements.
   • After merging, the sorted elements are copied back into the original array.

How Two Sorted Halves Are Merged:

When using Merge Sort, after recursively sorting the two halves of an array, we need to merge them into one sorted array.

Assume:

• Left subarray: sorted from index low to mid
• Right subarray: sorted from index mid + 1 to high

Merge Process:

1. Initialize pointers:

   • left → start of left half
   • right → start of right half
   • k → index to fill in the temporary array

2. Compare elements at left and right:

   • Add the smaller one to temp
   • Move the corresponding pointer

3. Continue this comparison until one side is exhausted.

4. Copy the remaining elements of the other half (if any) into the temp array.

5. Copy back the merged temp array into the original array from index low to high.

Example of how two sorted halves merged:

Let’s say we have:

• Left half: [2, 5, 9]
• Right half: [1, 6, 7]

We want to merge them into one sorted array.

Initial Pointers:

• left = 0 → points to 2
• right = 0 → points to 1
• temp = []

Merge Steps Table:

✅ Final Merged Result:
[1, 2, 5, 6, 7, 9]

Example:

Input: arr = [5, 4, 3, 2, 1]

Steps:

• Divide into [5, 4, 3] and [2, 1]
• Further divide [5, 4, 3] into [5, 4] and [3]
• [5, 4] → divide into [5] and [4] → merge to [4, 5]
• [4, 5] and [3] → merge to [3, 4, 5]
• [2, 1] → divide into [2] and [1] → merge to [1, 2]
• Merge [3, 4, 5] and [1, 2] → final result: [1, 2, 3, 4, 5]

✅ Final Sorted Array: [1, 2, 3, 4, 5]

Code:

public static void main(String[] args) {
    int[] arr = {5, 4, 3, 2, 1};
    mergeSort(arr, 0, arr.length - 1);
    System.out.println(Arrays.toString(arr));
}

static void mergeSort(int[] arr, int low, int high) {
    if (low >= high) {
        return;
    }

    int mid = (low + high) / 2;

    mergeSort(arr, low, mid);
    mergeSort(arr, mid + 1, high);

    merge(arr, low, mid, high);
}

static void merge(int[] arr, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];

    int left = low;
    int right = mid + 1;
    int k = 0;

    while (left <= mid && right <= high) {
        if (arr[left] <= arr[right]) {
            temp[k++] = arr[left++];
        } else {
            temp[k++] = arr[right++];
        }
    }

    while (left <= mid) {
        temp[k++] = arr[left++];
    }

    while (right <= high) {
        temp[k++] = arr[right++];
    }

    // Copy sorted temp back to original array
    for (int i = 0; i < temp.length; i++) {
        arr[low + i] = temp[i];
    }
}

---

Q 7. Quick Sort:

Given an unsorted array, our task is to sort it using the Quick Sort algorithm implemented recursively.

What is Quick Sort?

Quick Sort is a divide-and-conquer sorting algorithm. It works by choosing a pivot element and partitioning the array such that:

• All elements smaller than the pivot go to the left.
• All elements greater than the pivot go to the right.

This process is then recursively repeated on both sides.

How Quick Sort Works:

1. Choose a Pivot: In this implementation, we take the first element as the pivot.
2. Partition the Array:
   • Rearrange elements so that:
     • Left of pivot → smaller elements
     • Right of pivot → larger elements
   • The pivot is placed in its correct sorted position.
3. Recursively apply quick sort to the left and right parts of the array.

Partition Logic (First Element as Pivot):

In the partition function:

• Take the first element as the pivot.
• Initialize two pointers:
  • i = low, j = high
• Move i rightward until an element greater than pivot is found.
• Move j leftward until an element smaller than pivot is found.
• Swap arr[i] and arr[j] if i < j
• After the loop, swap the pivot (arr[low]) with arr[j].
• Return j → this is the final position of the pivot.

Example:

Input: arr = [7, 3, 1, 8, 2, 5]

Let’s go through one pass:

1. Pivot = 7 (first element)
2. i = 0, j = 5
3. Move i to the right until arr[i] > 7
   • arr[0]=7, arr[1]=3, arr[2]=1, arr[3]=8 → Stop at i=3
4. Move j to the left until arr[j] < 7
   • arr[5]=5, arr[4]=2 → Stop at j=4
5. Swap arr[3] and arr[4] → [7, 3, 1, 2, 8, 5]
6. Repeat until i >= j
7. Finally, swap pivot (7) with arr[j]
   → [5, 3, 1, 2, 7, 8]

Now 7 is at the correct position, and the process continues recursively on the left and right halves.

Advantages:

• Fast for large datasets
• In-place sort (does not require extra memory)

Disadvantages:

• Worst-case time complexity is O(n²)
• Quick Sort is not stable (relative order of equal elements may not be preserved)

Code:

public static void main(String[] args) {
    int[] arr = {7, 3, 1, 8, 2, 5};
    quickSort(arr, 0, arr.length - 1);
    System.out.println(Arrays.toString(arr));
}

static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

// First element as pivot
private static int partition(int[] arr, int low, int high) {
    int pivot = arr[low];
    int i = low;
    int j = high;

    while (i < j) {
        while (arr[i] <= pivot && i <= high - 1) {
            i++;
        }

        while (arr[j] >= pivot && j >= low + 1) {
            j--;
        }

        if (i < j) {
            // Swap arr[i] and arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // Swap pivot with arr[j]
    int temp = arr[j];
    arr[j] = arr[low];
    arr[low] = temp;

    return j; // pivot's final index
}

---

What's next:

I’m continuing this journey and will be:

• Posting blogs every 3 days.

• Also learning Web Development — check out my Web Dev Journey Blog.

• You can follow my journey on X (Twitter) where I post regular updates.

---

Conclusion:

By solving and understanding these seven fundamental problems — Recursive Linear Search, Binary Search, Search in Rotated Sorted Array, Bubble Sort, Selection Sort, Merge Sort, and Quick Sort — I’ve not only strengthened my problem-solving skills but also gained deep clarity on how recursion works and when to use it effectively.

Each problem taught me something unique:

• Recursive Linear Search helped me grasp the basics of recursion.
• Binary Search refined my understanding of divide-and-conquer logic.
• Search in Rotated Sorted Array challenged me to apply binary search in a modified scenario.
• Bubble and Selection Sort showed the importance of iterative thinking before diving into recursion.
• Merge Sort taught me how to split problems into subproblems and merge them recursively.
• Quick Sort helped me learn how partitioning works and how recursive sorting flows around a pivot.

This journey has cleared all my doubts about recursion, recursive tree calls, and breaking a problem down into smaller parts. I'm now much more confident in approaching any recursion-based or divide-and-conquer problem in the future.

🚀 From confusion to clarity — recursion now feels like a tool, not a mystery.

If you're also starting your DSA journey, I hope this blog helps you understand recursion better. Keep learning and keep coding!

If you're on a similar journey, feel free to reach out or follow along — we’re all in this together.