Sorting Algorithms

• Selection sort
• Bubble sort

Merge sort

Merge sort is O(n log(n)).

The steps are:

• If the array is less than two elements, return it
• Split the array in half.
• Call mergeSort on both halves.
• Merge the results from both left and right halves.
  • Create a new array to hold the sorted items
  • while there are still items in both arrays
    • If left is lesser pull it out and push it to the sorted list, otherwise do the right
  • If there are items remaining in one array, add them to the sorted list
• Return the merged results

Quicksort

Quicksort is O(n log(n)). It is also a destructive algorithm. It mutates the input list.

The steps are: