3.3 Space complexity

/**
* At least two points are deserve to consider.
* Point.1 : Normally, we need more auxiliary space when n increase.
* Point.2 : the recursion of function may be need more space.
*
* In my situation, the auxiliary space of Point.1 is n. For Point.2, Assume that the cost is A for ecah function call, the totally number of call is
* 2^0 + 2^1 + 2^2 + .....2^log2(n)
*
* then, the cost of point.2 is
*
* A*[1 + 2^1 + 2^2 + ....2^log2(n) ]
* =A*[1 + 2^1 + 2^2 + ....+ n]
* =A*[2*n-1] < A*2*n
*
* combine two parts:
* S(n) = O( B*n) = O(n)
*/
/*
* References
* wikipedia-Quicksort
*/

4. Merge sort

/****
* Merge Sort
* The common view is that: compare with famous Quicksort and Heapsort, it is slightly worse in sort a array. but it provide a excellent performance in sort a link list,

* which is difficult to Quicksort and Heapsort. on the other side, Mergesort is a stable sort, unlike standard in-place quicksort and heapsort. It's core principle is "divide

* and conquer".
*
* conceptually, Mergesort work as fellow:
* step1: divide the array into n sublists.That means every sublist is only contain of 1 element.
* step2: repeatedly merge all sublists to create new sorted sublist untill there is only 1 sublist remaining.
*
* just like this:
* step1: [0] [1] [2] [3] [4] [5] [6] [7]
* step2: [0...1] [2...3] [4...5] [6...7]
* step3: [0............3] [4..............7]
* step4: [0..................................7]
*
* If you need more information, there will be a good place.
* http://en.wikipedia.org/wiki/Merge_sort
*
* then , examine the core source code:
*/

4.1 core code

bool MergeSort::sort(void)
{
    ......
    int width = 1;
    while( width < (this->right - this->left + 1) )
    {
        this->subsort( width);	//sort sublists
        width *= 2;
    }
    .....
}

bool MergeSort::subsort( int width)
{
    .....
    INDEX	cur = this->left;
    while( cur + width <= this->right)
    {
        //sort two sublists into a new sorted list.
        this->sort2Arr( cur, width, cur + width, MIN( width, this->right-cur-width+1));
        cur += 2*width;
    }
    memcpy( this->array,  this->array_back, (this->right - this->left + 1)*sizeof(int));
    .....
}

4.2 Time complexity

/**
* Time complexity
*
* Now, let me see a interesting thing before check it's Time frequency. Image this, there are two arrays ,both of them are progressive increase. they are contain of n and

* m elements respectively.
*
* [1.............n] [1..........m]
*
* How many times is necessary to merge them into a new sorted array?
*
* -- at least: MIN( n,m);
* at most: m+n;
*
* For example:
* [ 1, 2, 3] [4,5,6,7]
* and
* [1,2,3,7] [4,5,6]
*
*
* Based on the conclusions above, we could know that : at worst situation, if we want to sort n elements by the way of Mergesort, the times of compare operation is n.
*
* So, Time frequency is n*log2(n)
* and
* T(n) = O( f(n)) = O( n*log2(n) )
*
*/

4.3 Space complexity

/**
* Space complexity
* In my example, a additional array was used to auxiliary operation.
* obviously, the space complexity is :
* S(n) = O(n);
*
* but that is at worst situation. It could be optimized.
*
*/

5. Heap sort

/****
* Heap Sort
* This is another famous sort algorithm. Need to say: it's very cool. Although sometimes it is slower in practice on most machine than well-implemented quicksort, it's

*have the advantage of a more favorable worst-case O( n*log(n)) runtime. unfortunately, it is not a stable sort.
*/