Sortable_List<Record>::recursive_merge_sort(Node<Record> *&sublist )
{
    if ( sublist  != 0 && sublist->next != 0 } //tức là có tồn tại 2 node trở lên để có thể chia đôi sublist được
    {
              Node <Record > *second_half = divide_from (sublist); 
              recursive_merge_sort(sublist) ;
              recursive_merge_sort(second_half) ;
              sublist = merge(sublist, second_half)
    }
}

Node<Record>* Sortable_List <Record>::divide_from( Node<Record> *sublist)
{
          Node<Record> *position , *midpoint , *second_half ;
          if (( midpoint = sublist) == NULL) return NULL ; // hổng có ds để chia 
          position  = midpoint->next ;
          while(position != 0) 
        {
                  position = position->next ;
                  if ( position  != 0)
                  {
                            midpoint = midpoint->next ;
                            position = position->next ;  
// midpoint duyêt 1 thì position duyệt 2 node cùng 1 lúc nên khi position kết thúc = NULL thì midpoint cũng đang ở vị trí chính giữa;
                  }
        }
          second_half = midpoint->next ;
          midpoint->next = NULL ;
          return second_half ;
}



Node <Record> * merge(Node<Record> *first , Node<Record>* second ) 
{
      Node<Record> *last_sorted ;
      Node<Record> combined ;
      last_sorted = &combined ;
      while ( first != NULL && second !=  NULL )
      {
              if (first->entry <= second->entry ) {
                        last_sortesorted->next = first ;
                        last_sorted = first ; 
                        first = first->next ;
              }
              else 
              {
                      last_sorted->next = second ; 
                      last_sorted = second ;
                      second = second->next ;
              }
        }
        if ( first == NULL ) 
              last_sorted->next = second ;
        else
              last_sorted-> next = first  ;
        return combind.next 
}

void Sortable_List<Record>::quick_sort()
{
          recursive_quick_sort(0 , count -1 ) ;
}

void Sortable_List<Record>::recursive_quick_sort(int low , int high )
{
          int pivot_position ;
          if (low < high )
          {
                    pivot_position = partition (low , high ) ;
                    recursive_quick_sort(low , high ) ;
                    recursive_quick_sort(pivot_position +1 , high ) ;
          }
}


int Sortable_List<Record>::partition(int low , int high ) 
{
              Record pivot ;
              int i , last_small;
              swap ( low , (low +high) /2 ;
              pivot = entry[low] ;
              last_small = low ;
              for ( i = low +1 ; i <= high ; i ++ )
              {
                        if(entry[i] < pivot )
                        {
                                    last_small = last_small +1 ;
                                    swap ( last_small , i ) ;
                        }
                
              }
                swap (low , last_small );
                return last_small ;
}

void Sortable_List<Record>::insert_heap(const Record ¤t, int low , int high ) 
{
              int large ; 
              large = 2*low+1 ;
              while ( large <= high ) {
                        if (large < high  && entry[large] < entry[large+1] )
                                    large ++ ;
                        if(current >= entry[large] ) 
                          {
                                break ;
                          }
                          else 
                          {
                                entry[low] = entry[large] ; 
                                low = large ;
                                large = 2 *  low + 1 ;
                          }
              }
              entry[low] = current ; 
}

Tạo ra heap lúc ban đầu , lúc chưa chạy giải thuật
void Sortable_List<Record>::bulidheap()
{
          int low ;
          for ( low = count / 2- 1; low >= 0 ; low -- )
          {
                  Record current = entry[low] ;
                  insert_heap(current, low, count -1) ;
          }
}

void Sortable_List<Record>::heapsort ()
{
            Record current ;
            int last_unsorted ;
            buildheap() ;
            for ( last_unsorted = count -1 ; last_unsorted > 0 ; last_unsorted -- )
            {
                      current = entry[ last_unsorted] ;
                      entry[last_unsorted]  = entry[0] ;
                      insert_heap(current,0,last_unsorted-1) ;
            }
}

void Sortable_List<Record>::insertion_sort() // phien bản nay list được hien thưc thông qua mảng chứ kg phải con trỏ 
{ 
    int  first_unsorted ;
    int position ;
    Record current ;
    for( first_unsorted = 1 ; first_unsorted < count ; first_unsorted ++)
    {
                if(entry[first_unsorted] < entry[first_unsorted-1])
                {
                        position = first_unsorted ;
                        current = entry[first_unsorted] ;
                        do {
                                    entry[position] = entry [ position -1] ;
                                    position -- ;
                        } while (position > 0 && entry[position-1]> current );
                        entry[position] = current ;
                }
      }
}

void Sortable_List<Record>::selectionsort() 
        {
                    for ( int position = count -1 ; position > 0 ; position -- ) 
                    {
                              int max = max_key(0,position) ; // tìm key lớn nhất 
                              swap (  max , position ) ; 
                    }
        }
        
        void Sortable_List<Record>::swap ( int low , int high)
        {
                    Record temp ;
                    temp = entry[low] ;
                    entry[low] = entry[high] ;
                    entry[high] = temp ;
        }
        
        .... max_key(int low , int high) 
        {
                int largest , current ;
                largest = low ;
                for ( current = low +1 ; current <= high ; current ++ )
                        if ( entry[largest] < entry[current] )
                        {
                                    largest = current ;
                          }
                  return largest ;
          }

void bublesort(double *a){
  double temp;
  for (int i = 2; i <= n; i++)
    for (int j = n; j >= i; j--)
      if (a[j] < a[j-1]) {
        temp = a[j];
        a[j] = a[j+1];
        a[j+1] = temp;
      }
}

double *distributioncounting(double *a){
  int c[M+1]; /* lưu số lần xuất hiện của các phần tử mảng a */
  int v;
  double b[n];
  for (int i = 0; i <= M; i++) c[i] = 0;
  for (i = 1; i <= n; i++) c[a[i]]++; /* đếm số lần xuất hiện của a[i] trong khoảng [0..M] */
  for (i = 1; i <= M; i++) c[i] += c[i-1]; /*tính vị trí cuối của mỗi đoạn con */
  for (i = n; i > 0; i--) {
    v = a[i];
    b[c[v]] = a[i];
    c[v]--;
  }
  return b;
}