Experimenting and Practice
// two nums array and a merged array
int[] nums1 = new int[]{ 1, 4, 5, 8 };
int[] nums2 = new int[]{ 2, 3, 6, 7 };
int[] merged = new int[8];
//setting counts so we can iterate through the elements separately
int countOne = 0;
int countTwo = 0;
int m = 0;
//iterates 7 times, as 8th iteration creates an outofbounds error because nums2[5] doesn't exist
for (int i = 0; i < 7; i++){
//if element in nums1 is bigger than the element in nums2
if (nums1[countOne] < nums2[countTwo]){
//sets the index of merged equal to nums1 element
merged[m] = nums1[countOne];
countOne++;
m++;
}
else {
//sets the index of merged equal to nums2 element
merged[m] = nums2[countTwo];
countTwo++;
m++;
}
}
//sets the last index of merged to last index of nums1
merged[7]= nums1[3];
//prints merge
for(int nums: merged){
System.out.print(nums);
}
// two nums array and a merged array
int[] nums1 = new int[]{ 1, 4, 5, 8 };
int[] nums2 = new int[]{ 2, 3, 6, 7 };
// finds length of both arrays
int totalLength = nums1.length + nums2.length;
int[] merged = new int[totalLength];
//iterate through merged and other arrays separately
int m = 0;
int countOne = 0;
int countTwo = 0;
for (int i = 0; i < totalLength; i++){
//if nums1 is empty
if(countOne == nums1.length){
//dumps rest of array into merged
for (int a = countTwo; a < nums2.length; a++){
merged[m] = nums2[a];
}
}
//if nums2 is empty
else if (countTwo == nums2.length){
//dumps rest of array into merged
for (int a = countOne; a < nums1.length; a++){
merged[m] = nums1[a];
}
}
else if (nums1[countOne] < nums2[countTwo]){
//sets the index of merged equal to nums1 element
merged[m] = nums1[countOne];
countOne++;
m++;
}
else {
//sets the index of merged equal to nums2 element
merged[m] = nums2[countTwo];
countTwo++;
m++;
}
}
for (int nums: merged){
System.out.print(nums);
}
import java.util.Random;
//instance of Random class
Random rand = new Random();
//creates an array with 5000 terms
int[] nums = new int[100];
//sets each element to a random number
for (int i = 0; i < nums.length; i++){
nums[i] = rand.nextInt(9);
}
//Print before sort
System.out.println("Before sort:");
for (int x: nums){
System.out.print(x);
}
//for each value through array
for (int i = 1; i < nums.length; i++){
//value at index i
int value = nums[i];
//value before index i
int a = i - 1;
//iterates while a>0 and the value before index i is greater than at index i
while (a >= 0 && nums[a] > value){
//moves larger value one index back (swaps position)
nums[a + 1] = nums[a];
a = a - 1;
}
//sets index to value
nums[a + 1] = value;
}
//Print after sort
System.out.println(" ");
System.out.println("After sort:");
for (int x: nums){
System.out.print(x);
}
import java.util.Random;
//instance of Random class
Random rand = new Random();
//creates an array with 5000 terms
int[] nums = new int[5000];
//sets each element to a random number
for (int i = 0; i < nums.length; i++){
nums[i] = rand.nextInt(9);
}
int comparisonCount = 0;
int swapCount = 0;
//gets time before program runs
long startTime = System.nanoTime();
//for each value through array
for (int i = 1; i < nums.length; i++){
//value at index i
int value = nums[i];
//value before index i
int a = i - 1;
//iterates while a>0 and the value before index i is greater than at index i
while (a >= 0 && nums[a] > value){
comparisonCount++;
//moves larger value one index back
nums[a + 1] = nums[a];
a = a - 1;
}
//sets index to value
nums[a + 1] = value;
swapCount++;
}
//gets time after
long endTime = System.nanoTime();
//total runtime
long totalTime = endTime - startTime;
System.out.println("Comparison Count: " + comparisonCount);
System.out.println("Swap Count: " + swapCount);
System.out.println(totalTime + " nanoseconds");
import java.util.Random;
public class MergeSort {
public static void merge(int[] arr, int left, int middle, int right) {
int n1 = middle - left + 1;
int n2 = right - middle;
// Create temporary arrays to store left and right sub-arrays
int[] leftArr = new int[n1];
int[] rightArr = new int[n2];
// Copy data from original array to left and right sub-arrays
System.arraycopy(arr, left, leftArr, 0, n1);
System.arraycopy(arr, middle + 1, rightArr, 0, n2);
// Merge the left and right sub-arrays
int i = 0;
int j = 0;
int k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
// Copy remaining elements from left and right sub-arrays, if any
while (i < n1) {
arr[k++] = leftArr[i++];
}
while (j < n2) {
arr[k++] = rightArr[j++];
}
}
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
// Find middle element
int middle = left + (right - left) / 2;
// Recursively sort left and right sub-arrays
mergeSort(arr, left, middle);
mergeSort(arr, middle + 1, right);
// Merge the sorted left and right sub-arrays
merge(arr, left, middle, right);
}
}
public static void main(String[] args) {
int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
int n = arr.length;
System.out.println("Original array:");
for (int num : arr) {
System.out.print(num + " ");
}
long startTime = System.nanoTime();
mergeSort(arr, 0, n - 1);
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println(" ");
System.out.println("\nSorted array:");
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println(" ");
System.out.println(totalTime + " nanoseconds");
}
}
MergeSort.main(null);
import java.util.Random;
public class MergeSort {
public static void merge(int[] arr, int left, int middle, int right) {
int n1 = middle - left + 1;
int n2 = right - middle;
// Create temporary arrays to store left and right sub-arrays
int[] leftArr = new int[n1];
int[] rightArr = new int[n2];
// Copy data from original array to left and right sub-arrays
System.arraycopy(arr, left, leftArr, 0, n1);
System.arraycopy(arr, middle + 1, rightArr, 0, n2);
// Merge the left and right sub-arrays
int i = 0;
int j = 0;
int k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
// Copy remaining elements from left and right sub-arrays, if any
while (i < n1) {
arr[k++] = leftArr[i++];
}
while (j < n2) {
arr[k++] = rightArr[j++];
}
}
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
// Find middle element
int middle = left + (right - left) / 2;
// Recursively sort left and right sub-arrays
mergeSort(arr, left, middle);
mergeSort(arr, middle + 1, right);
// Merge the sorted left and right sub-arrays
merge(arr, left, middle, right);
}
}
public static void main(String[] args) {
//creates an array with 5000 terms
int[] nums = new int[5000];
int n = nums.length;
//sets each element to a random number
for (int i = 0; i < nums.length; i++){
nums[i] = rand.nextInt(9);
}
long startTime = System.nanoTime();
mergeSort(nums, 0, n - 1);
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println(" ");
System.out.println(totalTime + " nanoseconds");
}
}
MergeSort.main(null);
Big O Ideas
- Merge Sort: O(n*logn)
- Insertion Sort: O(n^2)
Insertion sort takes roughly:
- 40300875 nanoseconds for a 5000 element array
- 7440250 nanoseconds for a 100 element array
Merge sort takes roughly:
- 4337333 nanoseconds for a 5000 element array
- 72083 nanoseconds for a 100 element array
Merge sort is better for larger arrays, while insertion sort is better for smaller arrays.