Manhattan life

上記の広告は１ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

The most direct competitor of quicksort is heapsort. Heapsort is typically somewhat slower than quicksort, but the worst-case running time is always O(n log n). Quicksort is usually faster, though there remains the chance of worst case performance except in the introsort variant. If it's known in advance that heapsort is going to be necessary, using it directly will be faster than waiting for introsort to switch to it. Heapsort also has the important advantage of using only constant additional space (heapsort is in-place), whereas even the best variant of quicksort uses Θ(log n) space. However, heapsort requires efficient random access to be practical.

Quicksort also competes with mergesort, another recursive sort algorithm but with the benefit of worst-case O(n log n) running time. Mergesort is a stable sort, unlike quicksort and heapsort, and can be easily adapted to operate on linked lists and very large lists stored on slow-to-access media such as disk storage or network attached storage. Although quicksort can be written to operate on linked lists, it will often suffer from poor pivot choices without random access. The main disadvantage of mergesort is that it requires Ω(n) auxiliary space in the best case, whereas the variant of quicksort with in-place partitioning and tail recursion uses only O(log n) space.

Memory usage patterns and index sorting
When the size of the array to be sorted approaches or exceeds the available primary memory, so that (much slower) disk or swap space must be employed, the memory usage pattern of a sorting algorithm becomes important, and an algorithm that might have been fairly efficient when the array fit easily in RAM may become impractical. In this scenario, the total number of comparisons becomes (relatively) less important, and the number of times sections of memory must be copied or swapped to and from the disk can dominate the performance characteristics of an algorithm. Thus, the number of passes and the localization of comparisons can be more important than the raw number of comparisons, since comparisons of nearby elements to one another happen at system bus speed (or, with caching, even at CPU speed), which, compared to disk speed, is virtually instantaneous.

For example, the popular recursive quicksort algorithm provides quite reasonable performance with adequate RAM, but due to the recursive way that it copies portions of the array it becomes much less practical when the array does not fit in RAM, because it may cause a number of slow copy or move operations to and from disk. In that scenario, another algorithm may be preferable even if it requires more total comparisons.

One way to work around this problem, which works well when complex records (such as in a relational database) are being sorted by a relatively small key field, is to create an index into the array and then sort the index, rather than the entire array. (A sorted version of the entire array can then be produced with one pass, reading from the index, but often even that is unnecessary, as having the sorted index is adequate.) Because the index is much smaller than the entire array, it may fit easily in memory where the entire array would not, effectively eliminating the disk-swapping problem. This procedure is sometimes called "tag sort".[2]

Another technique for overcoming the memory-size problem is to combine two algorithms in a way that takes advantages of the strength of each to improve overall performance. For instance, the array might be subdivided into chunks of a size that will fit easily in RAM (say, a few thousand elements), the chunks sorted using an efficient algorithm (such as quicksort or heapsort), and the results merged as per mergesort. This is less efficient than just doing mergesort in the first place, but it requires less physical RAM (to be practical) than a full quicksort on the whole array.

Techniques can also be combined. For sorting very large sets of data that vastly exceed system memory, even the index may need to be sorted using an algorithm or combination of algorithms designed to perform reasonably with virtual memory, i.e., to reduce the amount of swapping required.

http://en.wikipedia.org/wiki/Sorting_algorithm#Radix_sorthttp://www.experiencefestival.com/a/Quicksort_-_Competitive_sorting_algorithms/id/4693447

Basic concepts
Many algorithms that have the same efficiency do not have the same speed on the same input. First, algorithms must be judged based on their average case, best case, and worst case efficiency. Some algorithms, such as quick sort, perform exceptionally well for some inputs, but horribly for others. Other algorithms, such as merge sort, are unaffected by the order of input data. Even a modified version of bubble sort can finish in O(n) for the most favorable inputs.

A second factor is the "constant term". As big-O notation abstracts away many of the details of a process, it is quite useful for looking at the big picture. But one thing that gets dropped out is the constant in front of the expression: for instance, O(c*n) is just O(n). In the real world, the constant, c, will vary across different algorithms. A well-implemented quicksort should have a much smaller constant multiplier than heap sort.

In another word, the complexity of an algorithm (as shown in the above table) is not the whole story, however, because it does not take into account the constant of proportionality. For instance, the bubble sort is almost always much slower than any of the other N2 algorithms because it carries out a lot of redundant comparisons on each pass through the data. With this in mind, the list in which the algorithms were introduced was given in approximate order according to how they are expected to perform

A second criterion for judging algorithms is their space requirement -- do they require scratch space or can the array be sorted in place (without additional memory beyond a few variables)? Some algorithms never require extra space, whereas some are most easily understood when implemented with extra space (heap sort, for instance, can be done in place, but conceptually it is much easier to think of a separate heap). Space requirements may even depend on the data structure used (merge sort on arrays versus merge sort on linked lists, for instance).

Memory usage (and use of other computer resources). In particular, some sorting algorithms are "in place", such that only O(1) or O(log n) memory is needed beyond the items being sorted, while others need to create auxiliary locations for data to be temporarily stored.

A third criterion is stability -- does the sort preserve the order of keys with equal values? Most simple sorts do just this, but some sorts, such as heap sort, do not.

Name	Best	Average	Worst	Memory	Stable	Method	Other notes
Bubble sort	O(n²)	O(n²)	O(n²)	O(1)	Yes	Exchanging
Insertion sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Insertion	In the best case (already sorted), every insert requires constant time
Comb sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No	Exchanging	Small code size
Radix sort	O(n log n)	O(n log n)	O(n log n)	O(np)	Yes
Heapsort	O(n log n)	O(n log n)	O(n log n)	O(1)	No	Selection	By using input array as storage for the heap, it is possible to achieve constant space
Merge sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	Merging	On arrays, merge sort requires O(n) space; on linked lists, merge sort requires constant space
Quicksort	O(n log n)	O(n log n)	O(n²)	O(log n)	No	Partitioning	Randomly picking a pivot value (or shuffling the array prior to sorting) can help avoid worst case scenarios such as a perfectly sorted array.

Summary
The quicksort algorithm is generally considered to be the fastest of the N log(N) methods, although heapsort is more predictable and doesn't have the N2 worst-case that quicksort has. Merge sort can be an efficient algorithm, but is generally not preferred because of the extra space that it requires (which can also slow the algorithm down).

Time complexity observations
Quicksort and heapsort are good general sorting algorithms and should be the natural choice for more than a few hundred data items. Radix sorting methods are fairly complex and do not work in all cases, but they are also fast and could be the best choice in some specialised applications. Merge sort can work well if the items are in a linked list or provided as a string of numbers, but for most applications the extra space required discounts it from being an efficient solution. For small numbers of items, combsort is the simplest and one of the fastest methods available. Insertion sort also has some merits for small datasets. Bubble sort is probably only ever useful as a programming exercise!

Quicksort turns out to be the fastest sorting algorithm in practice. It has a time complexity of Θ(n log(n)) on the average. However, in the (very rare) worst case quicksort is as slow as Bubblesort, namely in Θ(n2). There are sorting algorithms with a time complexity of O(n log(n)) even in the worst case, e.g. Heapsort and Mergesort. But on the average, these algorithms are by a constant factor slower than quicksort.

It is possible to obtain a worst case complexity of O(n log(n)) with a variant of quicksort (by choosing the median as comparison element). But this algorithm is on the average and in the worst case by a constant factor slower than Heapsort or Mergesort; therefore, it is not interesting in practice.
--------
Algorithm mergesort has a time complexity of Θ(n log(n)) which is optimal. A drawback of mergesort is that it needs an additional space of Θ(n) for the temporary array b.

There are different possibilities to implement function merge. The most efficient of these variant requires only half as much additional space, it is faster than the other variants, and it is stable.
--------
With its time complexity of O(n log(n)) heapsort is optimal. Unlike mergesort, heapsort requires no extra space. On the other hand, heapsort is not stable. A sorting algorithm is stable, if it leaves the order of equal elements unchanged.

The heap data structure can also be used for an efficient implementation of a priority queue. A priority queue is an abstract list data structure with the operations insert and extractMax. With each element in the list a certain priority is associated. By insert an element together with its priority is inserted into the list. By extractMax the element with the highest priority is extracted from the list. Using a heap, both operations can be implemented in time O(log(n)).

Space complexity observations
For quicksort, the best- and average-case space-complexity is O(log(N)), for the stack-space used.

The worst-case space-complexity is O(N), but it can be limited to O(log(N)) if the code is modified so that the smaller half of the array is sorted first (and an explicit stack, or the tail-recursion optimisation, used).

In that case, the best-case space-complexity becomes O(1) [-- Andrew Clausen '05], "gcc -O2 does tail-recursion optimization, but -O1 doesn't."
--------
In any recursive method, space is required for the stack frames created by the recursive calls.

The maximum amount of memory required for the purpose is (size of the stack frame) * (depth of recursion)

The size of the stack frame is a constant, and for mergesort the depth of recursion (the number of levels) is O(log n).

The memory required for the stack frames is therefore O(log n).

Besides the given array, there are two temporary arrays allocated in each invocation whose total size is the same as the number of positions to be sorted: at level j this is p_j = n/2^j

This space is allocated before the recursive calls are made and needed after the recursive calls have returned and therefore the maximum total amount of space allocated is the sum of n/2^j for j=1 .. log(n).

This sum is O(n) - it is a little less than 2 * n.

Therefore, the space complexity of merge sort is O(n), but doubling the collection storage may sometimes be a problem.
--------
Heapsort doesn't need temporary storage space while sorting. Inside the MAX-HEAPIFY function, it calls MAX-HAEPIFY at the end and this is a recursion which requires O( 1) stack memory. There is possibility that at every level, the MAX-HEAPIFY becomes necessary. So, it is easily imagine that the space complexity would be O(lg n).

Taking a good look at the MAX-HEAPIFY step, we will find that the recursion is the last operation of the method MAX-HEAPIFY and thus, this is a, what so called, tail-recursion.

Tail-recursion can be replaced with a for loop to store the stack memory at the expense of costing more running time. The for loop only need constant space or O(1).

As such, heap sort space complexity is considered as O(1).

[Quote]:http://en.wikipedia.org/wiki/Stable_sort#Classificationhttp://64.233.167.104/search?q=cache:gasF96yX1NkJ:users.comlab.ox.ac.uk/ian.collier/rexxla/sorting/+heapsort+space+complexity&hl=en&ct=clnk&cd=47&gl=us&lr=lang_en|lang_ja&client=firefox-ahttp://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/quick/quicken.htm http://64.233.167.104/search?q=cache:oZR9SWgDVtoJ:www.inf.fh-flensburg.de/lang/algorithmen/sortieren/heap/heapen.htm+heapsort+space+complexity&hl=en&ct=clnk&cd=48&gl=us&lr=lang_en|lang_ja&client=firefox-ahttp://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html

Like merge sort, but unlike insertion sort, heapsort's running time is O(n lg n). Like insertion sort, but unlike merge sort, heapsort sorts in place: only a constant number of array elements are stored outside the input array at any time. Thus, heapsort combines the better attributes of the two sorting algorithms we have already discussed.

Heapsort also introduces another algorithm design technique: the use of data structure, in this case one we call a "heap", to manage information during the execution of the algorithm. Not only is the heap data structure useful for heapsort, but it also makes an effecient priority queue.

We note that the term "heap" was originally coined in the context of heapsort, but it has since come to refer to "garbage-collected storage:, such as the programming languages Lisp and Java provide. Our heap data structure is not garbage-collected storage, and whenever we refer to heaps here, we shall mean the structure.

The (binary) heap data structure is an array object that can be viewed as a nearly complete binary tree. Each node of the tree corresponds to an element of the array that stores the value in the node. The tree is completely, filled on all levels except possibly the lowest, which is filled from the left up to a point.

The root of the tree is A[1], and given the index i of a node, the indicies of its parent PARENT(i), left child LEFT(i) and right child RIGHT(i) can be computed simply.

PARENT(i)
return floor[ i/2 ]

LEFT(i)
return 2i

RIGHT(i)
return 2i + 1

On most computers, the LEFT procedure can compute 2i in one instruction by simply shifting the binary representation of i left one bit position. Similarly, the RIGHT procedure can quickly compute 2i + 1 by shifting the binary representation of i left one bit position and adding in a 1 as the low-order bit. The PARENT procedure can compute floor[ i/2 ] by shifting i right one bit position. In a good implementation of heapsort, these three procedures are often implemented as "macro" or "in-line" procedures.

There are two kinds of binary heaps: max-heaps and min-heaps. In both kinds, the values in the nodes satisfy a heap property, the specifics of which depend on the kind of heap. In a max-heap, the max-heap property is that for every node i other than the root,

A[PARENT(i)] ≧ A[i],

that is, the value of a node is at most the value of its parent. Thus, the largest element in a max-heap is stored at the root, and the sub-tree rooted at a node contains values no longer than that contained at the node itself. A min-heap is organized in the opposite way: the min-heap property is that for every node i other than the root,

A[PARENT(i)] ≦ A[i].

The smallest element in a min-heap is at the root.

For the heapsort algorithm, we use max-heaps. Min-heaps are commonly used in priority queues. We shall be precise in specifying whether we need a max-heap or a min-heap for any particular application, and when properties apply to either max-heaps or min-heaps, we just use the term "heap".

Viewing a heap as a tree, we define the height of a node in a heap to be the number of edges on the longest simple downward path from the node to a leaf, and we define the height of the heap to be the height of its root. Since a heap of n elements is based on a complete binary tree, its height is Θ(lg n). We shall see that the basic operations on heaps run in time at most proportional to the height o the tree and thus take O(lg n) time. The reminder of this article presents ive basic procedures and shows how they are used iun a strong algorithm and a priority-queue data structure.

・The NAX-HEAPIFY procedure, which runs in O(lg n) time, is the key to maintainingthe max-heap property.
・The BUILD-MAX-HEAP procedure, which runs in linear time, produces a max heap from an unordered input array.
・The HEAPSORT procedure, which runs in O(n lg n) time, sorts an array in place.
・The MAX-HEAP-INSERT, HEAP-EXTRACT-MAX, HEAP-INCREASE-KEY and HEAP-MAXIMUM procedures, which run in O(lg n) time, allow the heap data structure to be used as a priority queue.

Maintaining the heap property
MAX-HEAPIFY is an important subroutine fo rmanipulating max-heap. Its inputs are an array A and an index i into the array. When MAX-HEAPOFY is called, it is assumed that the library trees rooted at LEFT(i) and RIGHT(i) are max-heaps, but that A[i] may be smaller than its children, thus violating the max-heap property. The function of MAX-HEAPIFY is to let the alue at A[i] "float down" in the max-heap so that the sub-tree rooted at index i becomes a mac-heap.

The figures below illustrate the actions of MAX-HEAPIFY. At each step, the largest of the elements A[i], A[LEFT(i)] and A[RIGHT(i)] is determined, and its index is stored in largest. If A[i] is largest, then the subtree rooted at node i is max-heap and the procedure terminates. Otherwise, one of the two children has the largest element, and A[i] is swapped with A[largest]. which causes node i and its children to satisfy the max-heap property. The node indexed by largest, however, now has the original value A[i], and thus the subtree rooted at largest may violate the max-heap property. Consequently, MAX-HEAPIFY must be called recursively on that subtree.








The running time of MAX-HEAPIFY on a subtree of size n rooted at given node is Θ(1) time of fix up the relationships among the elements A[i], A[LEFT(i)], and A[RIGHT(i)], plus the time to run MAX-HEAPIFY on subtree rooted at one of the children of node i. The children's subtrees each have size at most 2n/3 (you can draw a tree to valify this) -- the worst case occurs when the last row of the tree is exactly half full -- and the running time of MAX-HEAPIFY can therefore be descried by the recurrence.

T(n) ≦ T(2n/3) + Θ(1).

The solution to this recurrence, by master theorem or intuitive tree analysis, is T(n) = O(lg n). Alternatively, we can characterize the running time of MAX-HEAPIFY on a node of height h as O(h).

Building a heap
We can use the procedure MAX-HEAPIFY in a button-up manner to convert an array A[1 .. n], where n = length[A], into a maz-heap. The elements in the subarray A(floor[n/2]+1) .. n] are all leaves of the tree, and so each is a 1-element heap to begin with. The procedure BUILD-HEAP goes through the remaining nodes of the tree and runs MAX-HEAPIFY on each one.

Figures below show an example of the action of BUILD-MAX-HEAP.






border="0" />


We can computer a simple upper bound on the running time of BUILD-MAX-HEAP as follows. Each call to MAX-HEAPIFY costs O(lg n) time, and there are O(n) such calls. Thus, the running time is O(n lg n). This upper bound, though correct, is not asymptotically tight.

We can derive a tighter bound by observing that the time for MAX-HEAPIFY to run at a node aries with the height of the node in the tree, and the heights of most nodes are small. Our tighter analysis relies on the properties that an n-element heap has height floor[lg n] and at most ceiling[n/2^h+1 nodes of any height h.

The time required by MAX-HEAPIFY when called on a node of height h is O(h), so we can express the total cost of BUILD-MAX-HEAP as being bounded from above by

p135

...

...

O(n).

Hence, we can build a max-heap from an unordered array in linear time.

The heapsort algorithm
The heapsort algorithm atarts by using BUILD-MAX_HEAP to build a max-heap on the input array A[1 .. n], where n = length[A]. Since the maximum element of the aray is stored at the root A[1], it can be put into its correct final position by exchanging it with A[n] If we now "disvard" node n from the heap, we observe that A[1 .. (n-1)] can easily be made into a max-heap. The children of the root remain max-heaps, but the new root element may violate the max-heap property. All that is needed to restore the max-heap property, however, is one call to MAX-HEAPIFY(A, 1), which leaves a max-heap in A[1 .. (n-1)]. The heapsort algorithm then repeats this process for the max-heap of size n-1 down to a heap of size 2.

#include "heapsort.h"
#include "windows.h"
#include <iostream>
using namespace std;
#define PARENT(i) ((i-1)/2)
#define LEFT(i)   ((2*i)+1)
#define RIGHT(i)  ((2*i)+2)

void Test::max_heapify(int A[], int i)
{
    int l = LEFT(i);
    int r = RIGHT(i);
    cout<<"l is "<<l<<"r is "<<r<<endl;
    int largest;
    if (l <= heap_size && A[l] > A[i])
        largest = l;
    else
        largest = i;
    if (r <= heap_size && A[r] > A[largest])
        largest = r;
    cout<<"largest is "<<largest<<endl;
    if (largest != i)
    {
        int tmp = A[i];
        A[i] = A[largest];
        A[largest] = tmp;
        max_heapify(A, largest);
    }
}

void Test::build_max_heap(int A[])
{
    heap_size = len;                    // at this phase, active heap size is the length of array A
    for (int i=(len-1)/2; i>=0; i--)
    {
        cout<<"i is "<<i<<endl;
        max_heapify(A, i);
    }
}

void Test::heapsort(int A[])
{
    build_max_heap(A);                // build heap only onece
    for (int i=len; i>0; i--)        // heapify once after every max element extraction
    {
        int tmp=A[0];
        A[0]=A[i];
        A[i]=tmp;
        heap_size = heap_size-1;    // active heap size decreases by 1.
                                                           // the rest are the numbers to be sorted.
        max_heapify(A, 0);
    }
}

The key operation of the merge sort algorithm is the merging of two sorted sequences in the "combine" step. To perform the merging, we use an auxiliary procedure MERGE(A, p, q, r), where A is an array and p, q and r are indices numbering elements of the array such that p ≦ q < r. The procedure assumes that the sub-arrays A[p...q] and A[q+1 .. r] are in sorted order. It merges them to form a single sorted sub-array that replaces the current sub-array A[p .. r].

#include "mergesort.h"
#include "limits.h"
#include <iostream>
using namespace std;

void Test::merge(int A[], int p, int q, int r)
{
    int n1 = q - p + 1;            // number of element at left  side
    int n2 = r - q;                // number of element at right side
    int *L = (int *)malloc(sizeof(int)*(n1+1));
    int *R = (int *)malloc(sizeof(int)*(n2+1));
    for (int i=0; i<n1; i++)
        L[i] = A[p + i];        // copy left  portion of A into L
    for (int j=0; j<n2; j++)
        R[j] = A[q + j + 1];    // copy right portion of A into R

    L[n1] = INT_MAX;            // left  pile sentinel
    R[n2] = INT_MAX;            // right pile sentinel
    int i = 0;
    int j = 0;
    for (int k=p; k<=r; k++)    // sort elments from both piles
    {
        if (L[i] <= R[j])
        {
            A[k] = L[i];
            i++;
        }
        else
        {
            A[k] = R[j];
            j++;
        }
    }   
}

void Test::mergesort(int A[], int p, int r)
{
    if (p < r)
    {
        int q = (p + r)/2;            // index of the halfway A
        mergesort(A,p,q);            // left  portion of A
        mergesort(A,q+1,r);            // right portion of A
        merge(A,p,q,r);                // sort
    }
}

Our MERGE procedure takes Θ(n), where n = r - p + 1 is the number of elements being merged, and it works as follows. Returning to our card-playing motif, suppose we have two piles of cards face up on a table. Each pile is sorted, with the smallest cards on top. We wish to merge the two piles into a single sorted output pile, which is to be face down on the table. Our basic step consisits of choosing the smaller of the two cards on top of the face-up piles, removing it from its pile. We repeat this step until one input pile is empty, at which time we just take the remaining input pile and place it face down onto the output pile. Computationally, each basic step takes constant time, merging takes Θ(n) time,




The following code implements te above idea, but with an additional twist that avoids having to check whether either pile is empty in each basic step. The idea is to put on the bottom of each pile a sentinel card, which contains a special value that we use to simplify our code. Here, we use ∞ as the sentinel value, so that whenever a card with ∞ is exposed, it cannot be the smaller card unles both piles have their sentinel cards exposed. But once that happens, all the non-sentinel cards have already been placed onto the output pile. Since we know in advance that exactly r - p + 1 cards will be placed onto the output pile, we can stop once we have performed that many basic steps.

In detail, the MERGE procedure works as follows. It computes the length n1 of the sub-array A[p .. q], and then computes the length n2 of the sub-array A[q+1 .. r]. We create arrays L and R of lengths n1+1 and n2+1, respectively. The first for loop copies the sub-array A[p .. q] into L[1 .. n1], and the second for loop copies the sub-array A[q+1 .. r] into R[1 .. n2]. Next, put the sentinels at the ends of the arrays L and R.

At the start of each iteration of the last for loop, the sub-array A[p .. k-1] contains the k - p smallest elements of L[1 .. n1 + 1] and R[1 .. n2 + 1], in sorted order. Moreover, L[i] and R[j] are the smallest elements of their arrays that have not been copied back into A.

To see that the MERGE procedure runs in Θ(n) time, where n = r - p + 1, observe that each of lines 1-3 and 8-11 takes constant time, the first two for loops take Θ(n1 + n2) = Θ(n) time, and there are n iterations of the last for loop, each of which takes constant time.

We can now use the MERGE procedure as a sub-routine in the merge sort algorithm. The procedure MERGE-SORT(A, p, r) sorts the elements in the sub-array A[p .. r]. If p ≧ r, the divide step simply computes an index q that partitions A[p .. r] into two sub-arrays: A[p .. q], containing ceiling of [n/2] elements, and A[q+1 .. r], containing floor of [n/2] elements.

To sort the entire sequence A= A[1], A[2] ,... A[n], we make the initial call MERGE-SORT(A, 1, length[A]), where once again length[A} = n. The algorithm consists of merging pairs of sequences of length 2 to ofrm sorted sequences of length 4, and so on, until two sequences of length n/2 are merged to form the final sorted sequence of length n.




Analyzing divide-and-conquer algorithms
When an algorithm contains a recursive call to itself, its running time can often be described by a recursive equation or recurrence, which describes the overall running time on a problem of size n in terms of the running time on smaller inputs. We can then use mathematical tools to solve the recursive and provide bounds on the performance of the algorithm.

Divide:D(n) = Θ(1)
Conquer:2T(n/2)
Conbine:C(n) = Θ(n)

When we add the functions D(n) and C(n) for the merge sort analysis, we are adding a function that is Θ(n) and a function that is Θ(1). This sum is a linear function of n, that is , Θ(n). Adding it to the 2T(n/2) term from the "conquer" step gives the recurrence for the worst-case running time T(n) of merge sort.

T(n) = Θ(1)                       if n = 1,
        = 2T(n/2) + Θ(n)      if n > 1.

Using the "master theorem", we can show that T(n) is Θ(n lg n). We do not need the master theorem to intuitively understand why the solution to the recurrence is T(n) = Θ(n lg n). Let us rewrite recurrence as below:

T(n) = c                             if n = 1,
            2T(n/2) + cn         if n > 1.

Finally, we apply the same approach as we took at the quicksort session.

we have T(n) = Θ(n lg n)

[Quote]: Introduction to Algorithms 2e.