[Intensicore]™

• Merge Sort

public int[] mergeSort(int array[])
// pre: array is full, all elements are valid integers (not null)
// post: array is sorted in ascending order (lowest to highest)
{
 // if the array has more than 1 element, we need to split it and merge the sorted halves
 if(array.length > 1)
 {
  // number of elements in sub-array 1
  // if odd, sub-array 1 has the smaller half of the elements
  // e.g. if 7 elements total, sub-array 1 will have 3, and sub-array 2 will have 4
  int elementsInA1 = array.length/2;
  // since we want an even split, we initialize the length of sub-array 2 to
  // equal the length of sub-array 1
  int elementsInA2 = elementsInA1;
  // if the array has an odd number of elements, let the second half take the extra one
  // see note (1)
  if((array.length % 2) == 1)
   elementsInA2 += 1;
  // declare and initialize the two arrays once we've determined their sizes
  int arr1[] = new int[elementsInA1];
  int arr2[] = new int[elementsInA2];
  // copy the first part of 'array' into 'arr1', causing arr1 to become full
  for(int i = 0; i < elementsInA1; i++)
   arr1[i] = array[i];
  // copy the remaining elements of 'array' into 'arr2', causing arr2 to become full
  for(int i = elementsInA1; i < elementsInA1 + elementsInA2; i++)
   arr2[i - elementsInA1] = array[i];
  // recursively call mergeSort on each of the two sub-arrays that we've just created
  // note: when mergeSort returns, arr1 and arr2 will both be sorted!
  // it's not magic, the merging is done below, that's how mergesort works :)
  arr1 = mergeSort(arr1);
  arr2 = mergeSort(arr2);
  
  // the three variables below are indexes that we'll need for merging
  // [i] stores the index of the main array. it will be used to let us
  // know where to place the smallest element from the two sub-arrays.
  // [j] stores the index of which element from arr1 is currently being compared
  // [k] stores the index of which element from arr2 is currently being compared
  int i = 0, j = 0, k = 0;
  // the below loop will run until one of the sub-arrays becomes empty
  // in my implementation, it means until the index equals the length of the sub-array
  while(arr1.length != j && arr2.length != k)
  {
   // if the current element of arr1 is less than current element of arr2
   if(arr1[j] < arr2[k])
   {
    // copy the current element of arr1 into the final array
    array[i] = arr1[j];
    // increase the index of the final array to avoid replacing the element
    // which we've just added
    i++;
    // increase the index of arr1 to avoid comparing the element
    // which we've just added
    j++;
   }
   // if the current element of arr2 is less than current element of arr1
   else
   {
    // copy the current element of arr1 into the final array
    array[i] = arr2[k];
    // increase the index of the final array to avoid replacing the element
    // which we've just added
    i++;
    // increase the index of arr2 to avoid comparing the element
    // which we've just added
    k++;
   }
  }
  // at this point, one of the sub-arrays has been exhausted and there are no more
  // elements in it to compare. this means that all the elements in the remaining
  // array are the highest (and sorted), so it's safe to copy them all into the
  // final array.
  while(arr1.length != j)
  {
   array[i] = arr1[j];
   i++;
   j++;
  }
  while(arr2.length != k)
  {
   array[i] = arr2[k];
   i++;
   k++;
  }
 }
 // return the sorted array to the caller of the function
 return array;
}

public int[] bubbleSort(int array[])
// pre: array is full, all elements are valid integers (not null)
// post: array is sorted in ascending order (lowest to highest)
{
 boolean swappedOnPrevRun = true;
 while(swappedOnPrevRun)
 {
  swappedOnPrevRun = false;   // this variable keeps track of whether to continue sorting or exit
  for(int i = 0; i < array.length - 1; i++) // loop through every element in the array,
        // except for the last one
  {
   if(array[i] > array[i + 1])  // if current element is greater than the next
   {
    // swap the two elements
    swappedOnPrevRun = true; // we don't want the loop to end just yet, we're not done
    int temp = array[i];  // store element i in a temporary variable
    array[i] = array[i + 1]; // set element i+1 to where i used to be
    array[i + 1] = temp;  // release the old i from temp into i+1 slot
   }
  }
 }
 return array;
}

Elements in red indicate swaps.
The green dash indicates return to position 0.

[3][5][4][9][2] -- original
-
[3][5][4][9][2] -- compare 3 to 5
[3][5][4][9][2] -- compare 5 to 4
[3][4][5][9][2] -- swap 4 and 5
[3][4][5][9][2] -- compare 5 to 9
[3][4][5][9][2] -- compare 9 to 2
[3][4][5][2][9] -- swap 2 and 9
-
[3][4][5][2][9] -- compare 3 to 4
[3][4][5][2][9] -- compare 4 to 5
[3][4][5][2][9] -- compare 5 to 2
[3][4][2][5][9] -- swap 2 and 5
[3][4][2][5][9] -- compare 5 to 9
-
[3][4][2][5][9] -- compare 3 to 4
[3][4][2][5][9] -- compare 4 to 2
[3][2][4][5][9] -- swap 2 and 4
[3][2][4][5][9] -- compare 4 to 5
[3][2][4][5][9] -- compare 5 to 9
-
[3][2][4][5][9] -- compare 3 to 2
[2][3][4][5][9] -- swap 2 and 3
[2][3][4][5][9] -- compare 3 to 4
[2][3][4][5][9] -- compare 4 to 5
[2][3][4][5][9] -- compare 5 to 9
-
[2][3][4][5][9] -- compare 2 to 3
[2][3][4][5][9] -- compare 3 to 4
[2][3][4][5][9] -- compare 4 to 5
[2][3][4][5][9] -- compare 5 to 9
[2][3][4][5][9] -- no changes (swaps) were made in the last run, so we are done!