# 2 way insertion sort, sorts but not as efficient as expected

The two-way insertion sort is a bi-directional insertion sort that sorts the array from the center out towards the ends.  My sort works but it is very inefficient.  We are tracking the amount of data moves as well as the amount of comparisons.

Expected approximate results
2-way insertion     4176550     4177731          72

2-way insertion         22862384    29116084             1531

The two-way insertion sort algorithm is:

do
if (A[left] > A[right])
swap A[left] and A[right]

starting with with A[right] and moving to the left, use insertion sort
algorithm to insert the element at A[right] into the correct location
between A[left+1] and A[right-1]

starting with A[left] and moving to the right, use the insertion sort
algorithm to insert the element at A[left] into the correct location
between A[left+1] and A[right-1]

left--, right++
until left has gone off the left edge of A and right has gone off the right
edge of A

Any ideas?

JOe K.
``````/*The two-way selection sort is a bi-directional insertion sort that
* sorts the array from the center out towards the ends.  The
* two-way insertion sort algorithm is:
*
* do
*
if (A[left] > A[right])
swap A[left] and A[right]

starting with with A[right] and moving to the left, use insertion sort
algorithm to insert the element at A[right] into the correct location
between A[left+1] and A[right-1]

starting with A[left] and moving to the right, use the insertion sort
algorithm to insert the element at A[left] into the correct location
between A[left+1] and A[right-1]

left--, right++
until left has gone off the left edge of A and right has gone off the right
edge of A
*/
public static <E extends Comparable<E>> void twoWayInsertSort(E[] A) {
if (A.length%2!=0){
throw new IllegalArgumentException();
}
int left = A.length/2-1;
int right = A.length/2+1;
int N = A.length/2;
int j = 0;
E tmpLeft, tmpRight;
//until left has gone off the left edge of A and right has gone off the right
//edge of A

//starting with with A[right] and moving to the left, use insertion sort
//algorithm to insert the element at A[right] into the correct location
//between A[left+1] and A[right-1]
for (int i = 1; i < N; i++){
for (int r = right; r > left; r--){
if(A[left].compareTo(A[right]) > 0){
swap(A, left, right);
}

dataMove++;
tmpRight = A[r];
j = r - 1;
while ((j >= left) && (A[j].compareTo(tmpRight) > 0)) {
dataMove++;
A[j+1] = A[j]; // move one value over one place to the right
j--;
}
dataMove++;
A[j+1] = tmpRight;    // insert kth value in correct place relative
}

for (int l = left; l < right; l++){
dataMove++;
tmpLeft = A[l];
j = l + 1;
while ((j <= right) && (A[j].compareTo(tmpLeft) < 0)) {
dataMove++;
A[j-1] = A[j]; // move one value over one place to the right
j++;
}
dataMove++;
A[j-1] = tmpLeft;    // insert kth value in correct place relative

}
left--;
right++;
}
}
``````
###### Who is Participating?

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
This is an O(n^3) algorithm, very inefficient.  That is, your while loops are nested inside two for loops, so they are getting executed a lot, and (correctly) counting up
dataMove each time.  You really need some kind of tree structure to do this sort of thing efficiently; inserting by sliding elements up means your doing an awful lot of moving.
0
Author Commented:
I have the original down pat which less efficient in it's compares but more efficient in it's data moves.

I just have no idea on how to increment these rights and lefts without that outer loop.
``````public static <E extends Comparable<E>> void insertionSort(E[] A) {
int k, j;
E tmp;
int N = A.length;

for (k = 1; k < N; k++) {
dataMove++;
tmp = A[k];
j = k - 1;
while ((j >= 0) && (A[j].compareTo(tmp) > 0)) {
dataMove++;
A[j+1] = A[j]; // move one value over one place to the right
j--;
}
dataMove++;
A[j+1] = tmp;    // insert kth value in correct place relative
// to previous values
}
}
``````
0
Fixer of ProblemsCommented:
When I had to do this, I made an index of the elements.  I swapped the index elements and never moved the data elements themselves.  It's a lot less moving.  When you're done, write out the data elements in index order.
0

Experts Exchange Solution brought to you by