algorithm to merge two sorted arrays without additional array

Algorithm to merge two sorted arrays: Here we use merge sort logic but with a small change; we take the larger size array and start inserting elements from end of that array.

package algorithms.sort;

/**
 * Algorithm to merge two sorted arrays without additional array,
 * provided one of the two arrays has the size of the combination
 * sizes of two arrays
 *
 * @author ntallapa
 *
 */
public class Merge2SortedArraysWO3rdArray {

	public void mergeArrays(int[] aArr, int aSize, int[] bArr, int bSize) {
		// pointer to end of the first sorted array
		int aIdx=aArr.length-1;
		// pointer to end of the second sorted array (pointer at 100 in below array bArr)
		int bIdx=bArr.length-aArr.length-1;
		// pointer to end of the second sorted array (pointer at last 0)
		int cIdx=bArr.length-1;

		/**
		 * whichever is higher in two arrays, place that
		 * element in last position of the bigger array
		 */
		while(cIdx>=0 && aIdx>=0 && bIdx>=0) {
			if(aArr[aIdx] > bArr[bIdx]) {
				bArr[cIdx--] = aArr[aIdx--];
			} else {
				bArr[cIdx--] = bArr[bIdx--];
			}
		}

		// run through the left over elements of array aArr
		while(aIdx>=0) {
			bArr[cIdx--] = aArr[aIdx--];
		}

		// run through the left over elements of array bArr
		while(bIdx>0) {
			bArr[cIdx--] = bArr[bIdx--];
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Merge2SortedArraysWO3rdArray mergeArrays = new Merge2SortedArraysWO3rdArray();
		int[] aArr = {3,7,12,16};
		int[] bArr = {1,4,9,100,0,0,0,0};

		mergeArrays.mergeArrays(aArr, aArr.length, bArr, bArr.length);

		for(int i: bArr) {
			System.out.println(i);
		}
	}
}

Output:

1 3 4 7 9 12 16 100
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Mawazo

Mostly technology with occasional sprinkling of other random thoughts

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

coding algorithms

"An approximate answer to the right problem is worth a good deal more than an exact answer to an approximate problem." -- John Tukey