sort

static void merge(T* left, T* mid, T* right){
    int n1 = mid - left + 1;
    int n2 = right - mid;
    T* lhs = new T[n1];
    T* rhs = new T[n2];
    for (int i = 0; i < n1; ++i){
        lhs[i] = *(left + i);
    }
    for (int j = 0; j < n2; ++j){
        rhs[j] = *(mid + 1 + j);
    }
    int i,j;
    i = 0;
    j = 0;
    T* k = left;
    while (i < n1 && j < n2){
        if (lhs[i] <= rhs[j]){
            *k = lhs[i];
            ++i;
        }
        else {
            *k = rhs[j];
            ++j;
        }
        k = k + 1;
    }

    while (i < n1){
        *k = lhs[i];
        ++i;
        ++k;
    }
    while (j < n2){
        *k = rhs[j];
        ++j;
        ++k;
    }
    Sorting::printArray(left,right);
}

static void mergeSort(T* start, T* end){
    if (start < end){
        T* mid = start + (end - start)/2;
        mergeSort(start,mid);
        mergeSort(mid+1,end);
        merge(start,mid,end);
    }
    return;

}

static void sortSegment(T* start, T* end, int segment_idx, int cur_segment_total) {
    int current = segment_idx + cur_segment_total;
    int walker = 0;
    while (current < (end-start)){
        T temp = start[current];
        walker = current - cur_segment_total;
        while (walker >= 0 && temp < start[walker]){
            start[walker + cur_segment_total] = start[walker];
            walker = walker - cur_segment_total;
        }
        start[walker + cur_segment_total] = temp;
        current = current + cur_segment_total;
    }
    return;
}

static void ShellSort(T* start, T* end, int* num_segment_list, int num_phases) {
    // TODO
    // Note: You must print out the array after sorting segments to check whether your algorithm is true.
    int segment = 1;
    int* k = (num_segment_list + num_phases - 1);
    while (num_phases > 0){
        segment = 1;
        while (segment <= *k){
            sortSegment(start,end,*k,segment);
            ++segment;
        }
        cout << *k << " segments: "; printArray(start,end);
        --num_phases;
        k = num_segment_list + num_phases - 1;
    }
}
template <class T>
void SLinkedList<T>::bubbleSort()
{
    if (this->count == 1) return;
    Node* list = this->head;
  //  bool flag = false;
   for (int i = 1; i < this->count; ++i){
   //    flag = false;
       while (list->next != NULL){
           if (list->data > list->next->data){
          //     flag = true;
               T temp = list->data;
               list->data = list->next->data;
               list->next->data = temp;
           }
           list = list->next;
       }
       this->printList();
       list = this->head;
   }

}