Tukukkk

I'm attempting to sort an array at the initial insertion of a value.
I tried to think "binary search", except with sorting, where I'm searching for the correct insertion point. I guess you can call it a binary sort, but its hardly that. It works just fine, but I wish it was faster. The slowest part of the algorithm is repositioning the previously inserted values.

I understand that there are already things in place that do what I'm trying to do. This was completely for the mental exercise. That being said, here's the code...

public void insert(int insertion) {

    int topEnd = nElem - 1;

    int bottomEnd = 0;

    int halfway;

    if (nElem == 0) {

        array[0] = insertion;

    } else

        while (true) {

            halfway = (topEnd + bottomEnd) / 2;





            // The following is a loop exiting case If topEnd and bottomEnd point to the same position,

            // or if topEnd minus bottomEnd equal -1 then you're ready to insert.



            if (topEnd == bottomEnd || topEnd - bottomEnd == -1) {





                /* For the following, if the number being inserted is greater, insert in front */



                if (insertion > array[halfway]) {

                    shift(bottomEnd, insertion);

                    array[halfway + 1] = insertion;

                    break;



                    /* For the following, if the number being inserted is lesser, insert behind */



                } else if (insertion < array[halfway]) {

                    shift(bottomEnd, insertion);

                    array[halfway] = insertion;

                    break;





                    /* For the following, if the number being inserted is equal, its a duplicate, insert in behind */



                } else if (insertion == array[halfway]) {

                    shift(bottomEnd, insertion);

                    array[halfway] = insertion;

                    break;

                }





                /* If we're not ready to insert, then we need to shorten our range.

                   If greater, shorten range by moving the bottom to halfway + 1.

                   If lesser, shorten the range by moving the top down to halfway - 1. */



            } else if (insertion > array[halfway]) {

                bottomEnd = halfway + 1;

            } else if (insertion < array[halfway]) {

                topEnd = halfway - 1;





                /*  The following is another loop exiting case that's meant to help handle duplicates.

                 *  If this case isn't in here when duplicates of more than two, or when topEnd equals 3, 7, 11, the

                 *  algorithm enters into an infinite loop. When testing this, it happened about 35% of the time.

                 * */



            } else if (insertion == array[halfway]) {

                shift(bottomEnd, insertion);

                array[halfway] = insertion;

                break;

            }

        }

    nElem++;

}

The following is the code for the slowest part of the algorithm. It's the shift method.

private void shift(int position, int value) {

    for (int i = nElem; i > position; i--)

        array[i] = array[i - 1];

}