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

my results (about 5x bigger)

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.

Expected approximate results

2-way insertion 4176550 4177731 72

my results (about 5x bigger)

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++;
}
}
```

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

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.

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
}
}
```

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trialAlso, although it would be a lot of work, the while loop on line 10 that's doing the comparisons could be replaced with a binary search (since you're searching the sorted part) and that would lower the time-complexity.

Of course this looks like an assignment to me, and I don't have a good guess as to what they're actually expecting from you.

Algorithms

From novice to tech pro — start learning today.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

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.