how to perform insertion sort recursively

Question

I have two methods that I intend to perform an insertion sort on an array of ints. The first method does the outer loop of the insertion sort algorithm while the second method inserts the particular element in the correct position recursively. For example:

int [] list = {20, 50, 30, 10, 60, 40};
sort(list);

The result should be {10,20,30,40,50,60} My problem is in the insert method; Here is my code:

public static void sort(int[] list) {
    int position;
    for (position = 1; position < list.length; position++) {
        insert(list, list[position], position);
    }
}

public static void insert(int[] list, int element, int position) {
    int position2 = position - 1;
    if (position == list.length - 1) {
        // do nothing
    } else {
        while ((position > 0) && (list[position - 1] > element)) {
            element = list[position - 1];
            insert(list, element, position - 1);
        }
        list[position] = element;
    }
}

Currently my output is,

 {20, 50, 50, 50, 60, 40}

I do not completely understand recursion. Please help

Answer 1

When you make some function recursive, there should be a recursion end condition along with other conditions.

Run this version and try to see what is that you're doing wrong.

Try this version:

public static void insertInOrder(int element, int[] a, int first, int last) {
    if (element >= a[last])
        a[last + 1] = element;
    else if (first < last) {
        a[last + 1] = a[last];
        insertInOrder(element, a, first, last - 1);
    } 
    else // first == last and element < a[last]
    {
        a[last + 1] = a[last];
        a[last] = element;
    }
}

public static void insertion_sort_recur(int[] arr, int first, int last) {
    if (first < last) {
        insertion_sort_recur(arr, first, last - 1); // avoids looping thru arr[0..last-1]
        insertInOrder(arr[last], arr, first, last - 1); // considers arr[last] as the first element in the unsorted list
    }
}

public static void main(String args[]) {
    int A[] = { 5, 3, 2, 4, 6, 1 };
    insertion_sort_recur(A, 0, 5);
    for(int i=0; i < A.length; i++) {
        System.out.println(A[i]);
    }
}

Source: http://analgorithmaday.blogspot.com/2011/01/insertion-sortrecursive-method.html

Answer 2

Try below code by providing else as an integer array, with sortedIndex as index of first element and and index as index of second element:

public static void insertionSort(int[] ele, int sortedIndex, int index) {
            if (sortedIndex < ele.length) {
                if (index < ele.length) {
                    if (ele[sortedIndex] > ele[index]) {
                        ele[sortedIndex] += ele[index];
                        ele[index] = ele[sortedIndex] - ele[index];
                        ele[sortedIndex] = ele[sortedIndex] - ele[index];
                    }
                    insertionSort(ele, sortedIndex, index + 1);
                    return;
                }
                if (index == ele.length) {
                    sortedIndex++;
                }
                insertionSort(ele, sortedIndex, sortedIndex + 1);
            }
        }