Swift-Sorting

Implementation for some sorting algorithms with Swift

1. Quicksort

   • Worst case performance O(n2)
   • Best case performance O(n log n) (simple partition) or O(n) (three-way partition and equal keys)
   • Average case performance O(n log n)
   • Worst case space complexity O(n) auxiliary (naive) O(log n) auxiliary

2. Mergesort

   • Worst case performance O(n log n)
   • Best case performance O(n log n) typical, O(n) natural variant
   • Average case performance O(n log n)
   • Worst case space complexity O(n) auxiliary

3. Heapsort

   • Worst case performance O(nlog n)
   • Best case performance Omega(n), O(nlog n)
   • Average case performance O(nlog n)
   • Worst case space complexity O(1) auxiliary

4. Bubble Sort

   • Worst case performance O(n^2)
   • Best case performance O(n)
   • Average case performance O(n^2)
   • Worst case space complexity O(1) auxiliary

5. Insertion Sort

   • Worst case performance О(n2) comparisons, swaps
   • Best case performance O(n) comparisons, O(1) swaps
   • Average case performance О(n2) comparisons, swaps
   • Worst case space complexity О(n) total, O(1) auxiliary

6. Selection Sort

   • Worst case performance О(n2)
   • Best case performance О(n2)
   • Average case performance О(n2)
   • Worst case space complexity О(n) total, O(1) auxiliary

More about Big O - http://bigocheatsheet.com