# -Insertion sort
###### tags: `Easy`

數組可分為[已排序]跟[未排序]
Insertion: 一直將未排序的插入已排序的
插入實作：通過比較大小作調換(swap)，直到要插入的點

#include <vector>
using namespace std;

vector<int> insertionSort(vector<int> array) {
  // Write your code here.
  if (array.empty()) return {};
  for (int i = 0; i < array.size(); i++){
      int j = i;
      while(j>0 && array[j]<array[j-1]){
          swap(array[j], array[j-1]);
          j -= 1;
      }
  }
  return array;
}