AP CSA 4.17 Exercise 1: Split It Until It Sorts Itself

AP CSA Hub Unit 4 4.1 ▼ Lesson Ex 1 Ex 2 Quiz 4.2 ▼ Lesson Ex 1 Ex 2 Quiz 4.3 ▼ Lesson Ex 1 Ex 2 Quiz 4.4 ▼ Lesson Ex 1 Ex 2 Quiz 4.5 ▼ Lesson Ex 1 Ex 2 Quiz 4.6 ▼ Lesson Ex 1 Ex 2 Quiz 4.7 ▼ Lesson Ex 1 Ex 2 Quiz 4.8 ▼ Lesson Ex 1 Ex 2 Quiz 4.9 ▼ Lesson Ex 1 Ex 2 Quiz 4.10 ▼ Lesson Ex 1 Ex 2 Quiz 4.11 ▼ Lesson Ex 1 Ex 2 Quiz 4.12 ▼ Lesson Ex 1 Ex 2 Quiz 4.13 ▼ Lesson Ex 1 Ex 2 Quiz 4.14 ▼ Lesson Ex 1 Ex 2 Quiz 4.15 ▼ Lesson Ex 1 Ex 2 Quiz 4.16 ▼ Lesson Ex 1 Ex 2 Quiz 4.17 ▼ Lesson Ex 1 Ex 2 Quiz

Unit 4: Data Collections · Lesson 4.17 · Exercise 1

Split It Until It Sorts Itself

Recursive Searching and Sorting. Write real Java, run it, and submit it to be graded against hidden test cases.

Back to the Lesson 4.17 page All Unit 4 lessons

Why this one is worth doing

A recursive binary search is the same idea as the iterative one, restated as a method that calls a smaller version of itself instead of looping. A recursive sort takes that further: mergeSort does not sort anything directly, it only trusts that a shorter mergeSort already did, and glues the two results together.

What to write

Read a count, then that many integers ALREADY sorted increasing, then a target value.
Write a RECURSIVE method binarySearch(data, target, low, high) that returns the index of target or -1. Print the result.
Write a second recursive method searchCalls(data, target, low, high) with the exact same recursive shape, that returns how many times the method was called, counting the call that finally returns. Print it.
Read a second count, then that many integers, unsorted.
Write a RECURSIVE method mergeSort(data) that returns a NEW sorted array: split the array in half, call mergeSort on each half, and merge the two sorted halves back together. Print the sorted result, values separated by single spaces.
binarySearch, searchCalls and mergeSort must each call themselves; do not use a loop inside any of the three. The step that merges two already-sorted halves back together is not the recursive part and may use a loop.

Your program reads

A count, then that many integers already sorted increasing, then a target, then a second count, then that many unsorted integers.

Your program prints

The binary search index, the recursive call count, then the merge sorted second array on one line.

Worked examples

These are the cases you can see. There are more you cannot, and they use different values, so an answer that prints these numbers as constants will fail.

Example 1 input

7
1 2 3 5 7 8 9
7
5
5 2 8 1 9

Example 1 output

4
3
1 2 5 8 9

Example 2 input

Example 2 output

0
1
7

Your answer

Main.java

import java.util.Scanner;

public class Main {
  public static int binarySearch(int[] data, int target, int low, int high) {
    return -1;
  }

  public static int searchCalls(int[] data, int target, int low, int high) {
    return 0;
  }

  public static int[] mergeSort(int[] data) {
    // Base case: length 0 or 1 is already sorted. Otherwise split, recurse, merge.
    return data;
  }

  private static int[] merge(int[] left, int[] right) {
    int[] out = new int[left.length + right.length];
    int i = 0;
    int j = 0;
    int k = 0;
    while (i < left.length && j < right.length) {
      if (left[i] <= right[j]) {
        out[k] = left[i];
        i = i + 1;
      } else {
        out[k] = right[j];
        j = j + 1;
      }
      k = k + 1;
    }
    while (i < left.length) {
      out[k] = left[i];
      i = i + 1;
      k = k + 1;
    }
    while (j < right.length) {
      out[k] = right[j];
      j = j + 1;
      k = k + 1;
    }
    return out;
  }

  public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    int count = input.nextInt();
    int[] data = new int[count];
    for (int i = 0; i < count; i++) {
      data[i] = input.nextInt();
    }
    int target = input.nextInt();

    // Call binarySearch and searchCalls here.

    int mCount = input.nextInt();
    int[] unsorted = new int[mCount];
    for (int i = 0; i < mCount; i++) {
      unsorted[i] = input.nextInt();
    }

    // Call mergeSort here and print the result space separated.
  }
}

Input for the Run button

Run sends whatever is in the input box below. Submitting runs your program against every test case, including hidden ones with different input.

Stuck?

Hint 1

binarySearch and searchCalls follow the exact same recursive shape as each other: one returns the answer, the other returns how many calls it took, including the call that finally returns.

Hint 2

mergeSort splits the array in half, calls itself on each half, and merges the two sorted results. The base case is an array of length 0 or 1, which is already sorted.

Hint 3

merge is given because combining two sorted halves is not the recursive part of merge sort; the recursion is entirely in how the array gets split down to that base case.

Where to go next

Rework the Lesson 4.17 page Pick another Unit 4 lesson

import java.util.Scanner;

public class Main {
  public static int binarySearch(int[] data, int target, int low, int high) {
    return -1;
  }

public static int searchCalls(int[] data, int target, int low, int high) {
    return 0;
  }

public static int[] mergeSort(int[] data) {
    // Base case: length 0 or 1 is already sorted. Otherwise split, recurse, merge.
    return data;
  }

private static int[] merge(int[] left, int[] right) {
    int[] out = new int[left.length + right.length];
    int i = 0;
    int j = 0;
    int k = 0;
    while (i < left.length && j < right.length) {
      if (left[i] <= right[j]) {
        out[k] = left[i];
        i = i + 1;
      } else {
        out[k] = right[j];
        j = j + 1;
      }
      k = k + 1;
    }
    while (i < left.length) {
      out[k] = left[i];
      i = i + 1;
      k = k + 1;
    }
    while (j < right.length) {
      out[k] = right[j];
      j = j + 1;
      k = k + 1;
    }
    return out;
  }

public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    int count = input.nextInt();
    int[] data = new int[count];
    for (int i = 0; i < count; i++) {
      data[i] = input.nextInt();
    }
    int target = input.nextInt();

// Call binarySearch and searchCalls here.

int mCount = input.nextInt();
    int[] unsorted = new int[mCount];
    for (int i = 0; i < mCount; i++) {
      unsorted[i] = input.nextInt();
    }

// Call mergeSort here and print the result space separated.
  }
}

Get in Touch

Whether you're a student, parent, or teacher — I'd love to hear from you.

Typically responds within 24 hours

✓

Message Sent!

Thanks for reaching out. I'll get back to you within 24 hours.

Name *

Email *

I am a... (optional)

Which course? (optional)

Phone (optional)

How did you find us? (optional)

🏫 Welcome, fellow educator!

I offer curriculum resources, practice materials, and study guides designed for AP CS teachers. Let me know what you're looking for — whether it's classroom materials, a guest speaker, or Teachers Pay Teachers resources.

Message (optional — leave blank if just subscribing)

✉

[email protected]

📚

Courses

AP CSA, CSP, & Cybersecurity

⏱

Response Time

Within 24 hours

Prefer email? Reach me directly at [email protected]