Sorting

Insertion Sort

Selection Sort

Merge Sort

Quick Sort

Bubble Sort

Merge sort - Java

Basic algorithm:
1. If list has one element, return;
2. Divide list in half
3. Sort first half
    Sort second half    (use recursion)
4. Merge sorted lists.

Best = Worst = O(nlogn)

Quick sort best = average = O(nlogn), worst = O(n^2)

Insertion sorting - Java

Insertion sorting:

 public static void insertionSort( int[] vals ) {
  int currInd;
  for (int pos=1; pos < vals.length; pos++) {
   currInd = pos;
   while (currInd > 0 && vals[currInd] < vals[currInd-1] ) {
    swap(vals, currInd, currInd-1);
    currInd--;
   }
  }
 }

Best: O(n)
Worst: O(n^2)

Java Built-in Sorting

Mergesort

import java.util.*;

public class MyBuiltInSortingTest {
    public static void main (String[] args) {
        Random random = new Random();
        List numsToSort = new ArrayList();
        
        for (int i=0; i < 5; i++) {
            numsToSort.add( random.nextInt(100) );
        }
        
        Collection.sort(numsToSort);
        System.out.println("New array after builtin sort: " + numsToSort.toString());
    }
}

Seletion Sort - Java

Steps:
Find smallest element, swap it with element at location 0;
Find next smallest element, swap it with element at location 1;
etc.

public static void selectionSort( int[] vals ) {
    int indexmin;

    for (int i = 0; i < vals.length-1; i++) {
        indexmin = i;
        for (int j = i+1; j < vals.length-2; j++) {
            if (vals[j] < vals[indexmin]) { indexmin = j; }
        }
        swap( vals, indexmin, j );
    }
}

Correctness:
Left array is always sorted.

Performance:
Time: O(n^2)
Space: O(1)

Note:
Not sensitive to already almost sorted array (takes same amount of time)
So Best = Worst = O(n^2)