Recently I systematicall review some sorting algorithms, including insertion sort, bubble sort, merge sort and quick sort. I then implement them in C++. All the function takes in a  vector<int>& type and directly operates on the input. To use the following code, you need to add the following code to your headers.

1 #include 
     
      2 #include 
      
       3 #include 
       
         // for randomization in quicksort4 5 using namespace std;
       
      
     

 Insertion Sort:

1 // Insertion sort2 void insertionSort(vector
     
      & arr) {3     for (int j = 1; j < (signed)arr.size(); j++)4         for (int i = j - 1; i >= 0 && arr[i] > arr[i + 1]; i--)5             swap(arr[i], arr[i + 1]);6 }
     

Bubble Sort:

1 // Bubble sort2 void bubbleSort(vector
     
      & arr) {3     for (int i = 0; i < (signed)arr.size() - 1; i++)4         for (int j = i + 1; j < (signed)arr.size(); j++)5             if (arr[i] > arr[j]) swap(arr[i], arr[j]);6 }
     

Merge Sort:

1 // Merge sort 2 void merge(vector
     
      & arr, int left, int mid, int right) { 3     if (left >= right) return; 4     vector
      
        larr(arr.begin() + left, arr.begin() + mid + 1); 5     vector
       
         rarr(arr.begin() + mid + 1, arr.begin() + right + 1); 6     int i = 0, j = 0, pos = left; 7     while(i < (signed)larr.size() && j < (signed)rarr.size()) { 8         if (larr[i] > rarr[j]) arr[pos++] = rarr[j++]; 9         else arr[pos++] = larr[i++];10     }11     while (i < (signed)larr.size()) arr[pos++] = larr[i++];12     while (j < (signed)rarr.size()) arr[pos++] = rarr[j++];13 }14 15 void mergeSortHelper(vector
        
         & arr, int left, int right) {16     if (left >= right) return;17     int mid = (left + right) / 2;18     mergeSortHelper(arr, left, mid);19     mergeSortHelper(arr, mid + 1, right);20     merge(arr, left, mid, right);21 }22 23 void mergeSort(vector
         
          & arr) {24     mergeSortHelper(arr, 0, arr.size() - 1);25 }
         
        
       
      
     

Quicksort:

1 // Quicksort 2 int partition(vector
     
      & arr, int left, int right) { 3     // Introduce randomization 4     srand((unsigned)time(0)); 5     int rndIdx = rand() % (right - left + 1) + left; 6     swap(arr[rndIdx], arr[left]); 7     int l = left + 1, r = right; 8     while (l <= r) { 9         if (arr[l] > arr[left] && arr[r] < arr[left])10             swap(arr[l], arr[r]);11         if (arr[l] <= arr[left]) l++;12         if (arr[r] >= arr[left]) r--;13     }14     swap(arr[left], arr[r]);15     return r;16 }17 18 void quickSortHelper(vector
      
        &arr, int left, int right) {19     if (left >= right) return;20     int pivot = partition(arr, left, right);21     quickSortHelper(arr, left, pivot - 1);22     quickSortHelper(arr, pivot + 1, right);23 }24 25 void quickSort(vector
       
        & arr) {26     quickSortHelper(arr, 0, arr.size() - 1);27 }
       
      
     

Welcome for any question, comment and suggestion about the code!