WHICH SORTING TECHNIQUE IS BETTER

Insertion Sort:
* Stable
* O(1) extra space
* O(n2) comparisons, O(n) time when nearly sorted

Selection Sort:
    * Not stable
    * O(1) extra space
    * Θ(n2) comparisons
    * Θ(n) swaps

Bubble Sort: 
    * Stable
    * O(1) extra space
    * O(n2) comparisons and swaps,O(n) when nearly sorted

Quick Sort:
    * Not stable
    * O(lg(n)) extra space (see discussion)
    * O(n2) time, but typically O(n·lg(n)) time

Merge Sort:

    # Stable
    # Θ(n) extra space for arrays (as shown)
    # Θ(lg(n)) extra space for linked lists
    # Θ(n·lg(n)) time