#ifndef __SORT_METHODS__
#define __SORT_METHODS__

#include <iostream>
#include <algorithm>

using namespace std;

namespace sort_methods{

      // 插入排序，对相对有序的序列，时间复杂度能达O(n)
      template<typename T>
      void insert_sort(T arr[], const int n){

           for(int i = 1; i < n; ++i){
                 int tmp = arr[i];
                 int j;
                 for(j = i; j > 0 && tmp < arr[j-1]; --j){
                      arr[j] = arr[j-1];
                 }

                 if(j != i){
                      swap(tmp, arr[j]);
                 }
           }
      }

      // 选择排序, O(n^2)
      template<typename T>
      void select_sort(T arr[], const int n){

           for(int i = 0; i < n; ++i){
                 int k = i;
                 for(int j = i+1; j < n; ++j){
                      if(arr[k] > arr[j]){
                            swap(k, j);
                      }
                 }

                 if(k != i){
                      swap(arr[k], arr[i]);
                 }
           }
      }

      //冒泡排序，时间复杂度O(n^2)
      template<typename T>
      void bubble_sort(T arr[], const int n){

           for(int i = 0; i < n; ++i){
                 for(int j = n-1; j > i; j--){
                      if(arr[j] < arr[j-1]){
                            swap(arr[j], arr[j-1]);
                      }
                 }
           }
      }


      template<typename T>
      void __merge(T arr[], const int l, const int m, const int r){

           // 归并数组
           T * tmp = new T [r-l+1];
           for(int i = l; i <= r; ++i){
                 tmp[i-l] = arr[i];
           }

           int i = l;
           int j = m+1;
           for(int k = l; k <= r; ++k){
                 if(i > m){
                      arr[k] = tmp[j-l];
                      ++j;
                 }else if(j > r){
                      arr[k] = tmp[i-l];
                      ++i;
                 }else if(tmp[i-l] < tmp[j-l]){
                      arr[k] = tmp[i-l];
                      ++i;
                 }else{
                      arr[k] = tmp[j-l];
                      ++j;
                 }
           }

           delete [] tmp;

      }

      template<typename T>
      void __merge_sort_topDown(T arr[], const int l, const int r){

           // 自顶向下归并排序
           if( l >= r ){
                 return;
           }

           int m = (l + r) / 2;
           __merge_sort_topDown(arr, l, m);
           __merge_sort_topDown(arr, m+1, r);
           if(arr[m] <= arr[m+1]){ // 剪枝优化, 如果已经有序，不需要进行归并
                 return;
           }
           __merge(arr, l, m, r);

      }

      // 自顶向下归并排序
      template<typename T>
      void merge_sort_topDown(T arr[], const int n){
           __merge_sort_topDown(arr, 0, n-1);
      }

      // 可以进行链表排序
      template<typename T>
      void merge_sort_bottomUp(T arr[], const int n){

           for(int size = 1; size <= n; size += size){
                 for(int i = 0; i + size < n; i += 2*size){
                      __merge(arr, i, i + size - 1, min(i + 2*size-1, n-1));

                 }
           }
      }

      // 对有重复元素较多的集合容易退化到 O(n^2)
      template<typename T>
      int partition1(T arr[], const int l, const int r){

           swap(arr[l], arr[rand() % (r-l+1) + l]);
           int j = l;
           for(int i = l+1; i <= r; ++i){
                 if(arr[l] > arr[i]){
                      swap(arr[i], arr[++j]);
                 }
           }

           swap(arr[l], arr[j]);
           return j;

      }

      template<typename T>
      void __quick_sort1(T arr[], const int l, const int r){

           if( l >= r ){
                 return;
           }

           int mid = partition1(arr, l, r);
           __quick_sort1(arr, l, mid-1);
           __quick_sort1(arr, mid+1, r);

      }


      template<typename T>
      void quick_sort1(T arr[], const int n){
           srand(time(NULL));
           __quick_sort1(arr, 0, n-1);
      }


      // 双路快速排序, 优化有重复元素的情况
      template<typename T>
      int partition2(T arr[], const int l, const int r){

           swap(arr[l], arr[rand() % (r-l+1) + l]);
           int i = l+1;
           int j = r;

           T tmp = arr[l];

           while(i <= j){

                 while(arr[i] < tmp && i <= j)++i;
                 while(arr[j] > tmp && i <= j)--j;
                 if(i <= j){
                      swap(arr[i], arr[j]);
                      ++i;
                      --j;
                 }
           }
           swap(arr[l], arr[j]);
           return j;

      }

      template<typename T>
      void __quick_sort2(T arr[], const int l, const int r){

           if( l >= r ){
                 return;
           }

           int mid = partition2(arr, l, r);
           __quick_sort2(arr, l, mid-1);
           __quick_sort2(arr, mid+1, r);

      }

      template<typename T>
      void quick_sort2(T arr[], const int n){
           srand(time(NULL));
           __quick_sort2(arr, 0, n-1);
      }

      // 三路快速排序， 不重复处理排序好的重复的元素
      template<typename T>
      void __quick_sort3(T arr[], const int l, const int r){

           if( l >= r ){
                 return;
           }

           // partition
           swap(arr[l], arr[rand() % (r-l+1) + l]);
           int tmp = arr[l];
           int lt = l;
           int gt = r + 1;
           int i = l + 1;
           while(i < gt){

                 if(arr[i] < tmp){
                      swap(arr[i++], arr[++lt]);
                 }else if(arr[i] > tmp){
                      swap(arr[i], arr[--gt]);
                 }else{
                      ++i;
                 }
           }

           swap(arr[l], arr[lt]);
           __quick_sort3(arr, l, lt-1);
           __quick_sort3(arr, gt, r);
      }

      template<typename T>
      void quick_sort3(T arr[], const int n){
           srand(time(NULL));
           __quick_sort3(arr, 0, n-1);
      }
};
#endif