Page 250 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 12: Sorting

i). The procedure build-initial-heap calls the adjust procedure for values of i ranging from n/2 Notes
down to 1. Hence the total number of iterations will be:
n /2
n
n
ni
nn
n
+
log( ) log( /2) .....log( / /2) = ∑ log( / ) = n /2log( )– log(! /2)
n
+
i= 1
This comes out to be some constant times n. Hence the computation time of build_initial_heap is
O(n). The heapsort procedure calls adjust (x, 1, i) (n-1) times, hence the total number of iterations
made in the heap sort will be:
n− 1
∑ log( /1)
i
i= 1
n− 1
∑ log( ) = log(1) log(2) ..... log( – 1)
+
i
+
n
+
i= 1
which comes out to be approx. n log(n). Hence the computing time of heapsort is O(n log(n)) +
O(n).
The only additional space needed by heap sort is space for one record to carry out exchange.
Consider a list given below when heapsort is applied to it we get following:
42 97
32 58
48 75
20 53
58 42
53 53

75 48
53 32
97 20
list to be sorted initial heap

Output after each pass of heapsort
75 58 53 53 48 42 32 20
58 53 48 48 42 32 20 32
53 53 53 20 20 20 42 42
53 32 32 32 32 48 48 48
42 42 42 42 53 53 53 53
20 20 20 53 53 53 53 53
48 48 58 58 58 58 58 58
32 75 75 75 75 75 75 75
97 97 97 97 97 97 97 97

12.5 Merge Sort

This is another sorting technique having the same average and worst case time complexity,
requiring an additional list of size n. The technique that we use is the merging of the two sorted
lists of size m and n respectively to form a single sorted list of size (m+n). Given a list of size n to
be sorted, instead of viewing it to be one single list of size n, we start by viewing it to be n lists

LOVELY PROFESSIONAL UNIVERSITY 245