cs325/hw2/mergesort3time.cpp
//GeeksforGeeks used as a reference for how to do merge sort in thirds
//The merge function that merges 3 parts
GeeksforGeeks used as a reference for how to do merge sort in thirds
The merge function that merges 3 parts
GeeksforGeeks used as a reference for how to do merge sort in thirds The merge function that merges 3 parts
void merge(int origArray[], int lowBound, int firstMid, int secondMid, int upBound, int sortedArray[]) {
	int firstIndex = lowBound;
  	int secondIndex = firstMid;
  	int thirdIndex = secondMid;
  	int sortedIndex = lowBound;
	while (firstIndex < firstMid && secondIndex < secondMid && thirdIndex < upBound) {
		if(origArray[firstIndex] < origArray[secondIndex]) {
			if(origArray[firstIndex] < origArray[thirdIndex]) {
				sortedArray[sortedIndex] = origArray[firstIndex];
        		sortedIndex++;
        		firstIndex++;
			} else {
				sortedArray[sortedIndex] = origArray[thirdIndex];
        		sortedIndex++;
        		thirdIndex++;
			}
		} else {
			if(origArray[secondIndex] < origArray[thirdIndex]) {
				sortedArray[sortedIndex] = origArray[secondIndex];
        		sortedIndex++;
        		secondIndex++;
			} else { 
				sortedArray[sortedIndex] = origArray[thirdIndex];
        		sortedIndex++;
        		thirdIndex++;
			}
		}
	}
	while (firstIndex < firstMid && secondIndex < secondMid) {
		if(origArray[firstIndex] < origArray[secondIndex]) {
			sortedArray[sortedIndex] = origArray[firstIndex];
      		sortedIndex++;
      		firstIndex++;
		} else { 
			sortedArray[sortedIndex] = origArray[secondIndex];
      		sortedIndex++;
      		secondIndex++;
		}
	}
	while (firstIndex < firstMid && thirdIndex < upBound) {
		if(origArray[firstIndex] < origArray[thirdIndex]) {
			sortedArray[sortedIndex] = origArray[firstIndex];
      		sortedIndex++;
      		firstIndex++;
		} else { 
			sortedArray[sortedIndex] = origArray[thirdIndex];
      		sortedIndex++;
      		thirdIndex++;
		}
	}
	while (secondIndex < secondMid && thirdIndex < upBound) {
		if(origArray[secondIndex] < origArray[thirdIndex]) {
			sortedArray[sortedIndex] = origArray[secondIndex];
      		sortedIndex++;
      		secondIndex++;
		} else { 
			sortedArray[sortedIndex] = origArray[thirdIndex];
      		sortedIndex++;
      		thirdIndex++;
		}
	}
	if (firstIndex < firstMid) {
    	for(int i = 0; i < (firstMid - firstIndex); i++) {
      		sortedArray[sortedIndex] = origArray[firstIndex];
      		sortedIndex++;
      		firstIndex++;
    	}
  	}
	if (secondIndex < secondMid) {
    	for (int i = 0; i < (secondMid - secondIndex); i++) {
      		sortedArray[sortedIndex] = origArray[secondIndex];
      		sortedIndex++;
      		secondIndex++;
    	}
  	}
	if (thirdIndex < upBound) {
    	for (int i = 0; i < (upBound - thirdIndex); i++) {
      		sortedArray[sortedIndex] = origArray[thirdIndex];
      		sortedIndex++;
      		thirdIndex++;
    	}
  	}
}
void merge ( int origArray [ ] , int lowBound , int firstMid , int secondMid , int upBound , int sortedArray [ ] ) { int firstIndex = lowBound ; int secondIndex = firstMid ; int thirdIndex = secondMid ; int sortedIndex = lowBound ; while ( firstIndex < firstMid && secondIndex < secondMid && thirdIndex < upBound ) { if ( origArray [ firstIndex ] < origArray [ secondIndex ] ) { if ( origArray [ firstIndex ] < origArray [ thirdIndex ] ) { sortedArray [ sortedIndex ] = origArray [ firstIndex ] ; sortedIndex ++ ; firstIndex ++ ; } else { sortedArray [ sortedIndex ] = origArray [ thirdIndex ] ; sortedIndex ++ ; thirdIndex ++ ; } } else { if ( origArray [ secondIndex ] < origArray [ thirdIndex ] ) { sortedArray [ sortedIndex ] = origArray [ secondIndex ] ; sortedIndex ++ ; secondIndex ++ ; } else { sortedArray [ sortedIndex ] = origArray [ thirdIndex ] ; sortedIndex ++ ; thirdIndex ++ ; } } } while ( firstIndex < firstMid && secondIndex < secondMid ) { if ( origArray [ firstIndex ] < origArray [ secondIndex ] ) { sortedArray [ sortedIndex ] = origArray [ firstIndex ] ; sortedIndex ++ ; firstIndex ++ ; } else { sortedArray [ sortedIndex ] = origArray [ secondIndex ] ; sortedIndex ++ ; secondIndex ++ ; } } while ( firstIndex < firstMid && thirdIndex < upBound ) { if ( origArray [ firstIndex ] < origArray [ thirdIndex ] ) { sortedArray [ sortedIndex ] = origArray [ firstIndex ] ; sortedIndex ++ ; firstIndex ++ ; } else { sortedArray [ sortedIndex ] = origArray [ thirdIndex ] ; sortedIndex ++ ; thirdIndex ++ ; } } while ( secondIndex < secondMid && thirdIndex < upBound ) { if ( origArray [ secondIndex ] < origArray [ thirdIndex ] ) { sortedArray [ sortedIndex ] = origArray [ secondIndex ] ; sortedIndex ++ ; secondIndex ++ ; } else { sortedArray [ sortedIndex ] = origArray [ thirdIndex ] ; sortedIndex ++ ; thirdIndex ++ ; } } if ( firstIndex < firstMid ) { for ( int i = 0 ; i < ( firstMid - firstIndex ) ; i ++ ) { sortedArray [ sortedIndex ] = origArray [ firstIndex ] ; sortedIndex ++ ; firstIndex ++ ; } } if ( secondIndex < secondMid ) { for ( int i = 0 ; i < ( secondMid - secondIndex ) ; i ++ ) { sortedArray [ sortedIndex ] = origArray [ secondIndex ] ; sortedIndex ++ ; secondIndex ++ ; } } if ( thirdIndex < upBound ) { for ( int i = 0 ; i < ( upBound - thirdIndex ) ; i ++ ) { sortedArray [ sortedIndex ] = origArray [ thirdIndex ] ; sortedIndex ++ ; thirdIndex ++ ; } } }
GeeksforGeeks used as a reference for how to do merge sort in thirds
The merge function that merges 3 parts
GeeksforGeeks used as a reference for how to do merge sort in thirds The merge function that merges 3 parts
//Initialize the bounds, these are used instead of splitting one array into 3 arrays //This while loop will run while there is a smaller value in all three thirds of the array //This if statement will check if the int from the first third is less than the int from the second third //If that's true, this if will check if the int from the first third is less than the int from the third third //If the int from the first third is the smallest, then it's added to the sorted array //The indexes for both the sorted array and the first third are incremented //If the int from the third third is the smallest, then that int is added to the sorted array //The indexes for both the sorted array and the third third are incremented //If the int from the second third is smaller than the int from the first third, this else is entered //The int from the second third and the int from the third third are now compared //If the int from the second third is smaller, it's added to the sorted array //The indexes are incremented //If the int from the third third is the smallest, it gets added to the sorted array //The indexes are incremented //If there are any remaining ints in the first and second thirds, this while loop is entered //Check if the int from the first third is smaller than the int from the second third //If it is, the int from the first third is added to the sorted array //The indexes are incremented //If the int from the second third is smaller, it gets added to the sorted array //The indexes are incremented //If there are still ints in the first and third thirds, this while loop is entered //check if the int from the first third is smaller than the int from the third third //If it is, the int from the first third is added to the sorted array //The indexes are incremented //If not, the int from the third third is added to the sorted array //The indexes are incremented //If there are still ints in the second and thir thirds, this while loop is entered //Check if the int from the second third is smaller than the int from the third third //If it is, the int from the second third is added to the sorted array //The indexes are incremented //If not, the int from the third third is added to the sorted array //The indexes are incremented //If the firstIndex is less than the first midpoint, there are still values to be sorted from the first third //For loop runs however many values are left //The ints get added to the sorted array //The indexes are incremented //If the secondIndex is less than the second midpoint, there are still values to be sorted from the second third //For loop runs however many values are left //The ints get added to the sorted array //The indexes are incremented //If the thirdIndex is less than the upper bound, there are still values to be sorted from the third third //For loop runs however many values are left //The ints get added to the sorted array //The indexes are incremented