cs325/hw1/mergesort.cpp
//The merge function that connects two pieces of an array
The merge function that connects two pieces of an array
The merge function that connects two pieces of an array
void merge(int *arr, int leftBound, int mid, int rightBound) {
	int leftArrSize = mid - leftBound + 1;
	int L[leftArrSize];
	int rightArrSize = rightBound - mid;
	int R[rightArrSize];
	for (int i = 0; i < leftArrSize; i++) {
		L[i] = arr[leftBound + i];
	}
	for (int j = 0; j < rightArrSize; j++) {
		R[j] = arr[mid + 1 + j];
	}
	int leftI = 0, rightI = 0, mainI = leftBound;
	while (leftI < leftArrSize && rightI < rightArrSize) {
		if (L[leftI] <= R[rightI]) {
			arr[mainI] = L[leftI];
			leftI++;
		} else {
			arr[mainI] = R[rightI];
			rightI++;
		}
		mainI++;
	}
	while (leftI < leftArrSize) { 
		arr[mainI] = L[leftI];
		leftI++;
		mainI++;
	}
	while (rightI < leftArrSize) { 
		arr[mainI] = R[rightI];
		rightI++;
		mainI++;
	} 
}
void merge ( int * arr , int leftBound , int mid , int rightBound ) { int leftArrSize = mid - leftBound + 1 ; int L [ leftArrSize ] ; int rightArrSize = rightBound - mid ; int R [ rightArrSize ] ; for ( int i = 0 ; i < leftArrSize ; i ++ ) { L [ i ] = arr [ leftBound + i ] ; } for ( int j = 0 ; j < rightArrSize ; j ++ ) { R [ j ] = arr [ mid + 1 + j ] ; } int leftI = 0 , rightI = 0 , mainI = leftBound ; while ( leftI < leftArrSize && rightI < rightArrSize ) { if ( L [ leftI ] <= R [ rightI ] ) { arr [ mainI ] = L [ leftI ] ; leftI ++ ; } else { arr [ mainI ] = R [ rightI ] ; rightI ++ ; } mainI ++ ; } while ( leftI < leftArrSize ) { arr [ mainI ] = L [ leftI ] ; leftI ++ ; mainI ++ ; } while ( rightI < leftArrSize ) { arr [ mainI ] = R [ rightI ] ; rightI ++ ; mainI ++ ; } }
The merge function that connects two pieces of an array
The merge function that connects two pieces of an array
//Intialize left array size //Create a Left array //Initialize right array size //Create a right array //Copy data into left and right arrays //Intialize indexes to appropriate values //Sort the pieces of the array //Check if the left value is less than or equal to the right value //If so, add the left value to the main array //Increase the i index //If not, add the right value to the main array //Increase the j index //Increase the main array index after the new value has been added //Copy any remaining values //If the left index is less than the total size of the left half, the rest of the values are added to the main array //Both indexes are increased to account for however many values were added //Copy any remaining values //If the right index is less than the total size of the left half, the rest of the values are added to the main array //Both indexes are increased to account for however many values were added