Q:

How do I make a sort method using recursion?

I'm learning recursion and I was instructed to make a recursive method that sorts an array. So far I have this:
public static void sort(int [] a, int i) {
    if(i == a.length - 1){
        System.out.println(a[i]);
    }
    if(i < a.length) {
        if(a[i] > a[i+1]) {
            int temp = a[i+1];
            a[i+1] = a[i];
            a[i] = temp;
            sort(a,i++);
        }
        printArray(a); 
    }
}

Now I know this is wrong because I still really don't quite understand how to use recursion in my programming. If someone could just help me with the method I would appreciate it, but and explanation on how to use recursion in my programming would be great. Thank you in advance.

A:

To write a recursive algorithm, you need to think along these lines: How can I solve the problem by solving one or more smaller instances of the same problem?  For a problem like "sort an array of N integers", the smaller problem could be an array of N-1 integers, or it could be two arrays of N/2 integers (roughly), or other possibilities.
Since you weren't give any other hints, the simplest thing would be: OK, I have an array of N integers.  Let's say I sorted the last N-1 integers, so that my array would look like
------------------------------------------------|
| a[0]         | a[1] | a[2] | ...... | a[N-1]  |
------------------------------------------------|
| out of order | ......... all sorted ......... | 

If you could do that, then since you only have one out-of-order element, you should be able to figure out how to swap elements to get a[0] in the right place. 
So now the outline of a method looks like this:
void sort(int[] a, int i) {   // sort the elements from a[i] to a[N-1]
    if (i <= a.length - 2) {
        // Solve the smaller problem recursively.  But if the smaller problem is
        // only 0 or 1 elements, there's nothing else to do.
        sort (a, i + 1);      
    }
    // At this point, we've sorted elements from a[i+1] to a[N-1].  Now a[i] is
    // out of order; write logic that exchanges elements to get a[i] in the right
    // place.
}

Another possible approach: Instead of sorting the N-1 elements first, you could find the smallest element, move it to the beginning of the array, so that your array looks like
--------------------------------------------|
| a[0]     | a[1] | a[2] | ...... | a[N-1]  |
--------------------------------------------|
| in order | ........ out of order ........ | 

and then call the method recursively to sort the N-1 elements a[1] to a[N-1], and then you're done.
I think you started out on the right track; you just need to visualize the problem in the correct way, which takes a little practice.

