Unit II

Searching and Sorting Algorithms

2.1 Algorithms: Analysis of Iterative and Recursive algorithms, Space & Time complexity, Asymptotic notation- Big-O, Theta and Omega notations.

Analysis of Iterative Algorithms

Complexity of an algorithm is the function which gives the running time and space requirement of an algorithm in terms of size of input data. Frequency count refers to the number of times particular instructions executed in a block of code. Frequency count plays important role in the performance analysis of an algorithm. Each instruction in algorithm is incremented by one as its execution. Frequency count analysis is the form of priori analysis. Frequency count analysis produces output in terms of time complexity and space complexity.

Frequency count analysis for this code is as follows

 In the above example, for the first four instructions there is no frequency count. For data declaration and the inclusion of header file there is no frequency count. So, for this example has a frequency count for time is 2 and a frequency count for space is 1. So, total frequency count is 3.

 Consider the following example

 Explanation : In the above example, one is add to frequency count for instruction four and seven after that in fifth instruction is check from zero to five so it will add value six to frequency count. ‘For’ loop executed for five times so for  sixth instruction frequency count is five. Total frequency count for above program is 1+6+5+1 =13.

Consider the following example

 Explanation : In the above example, in instruction five value of ‘i’ is check from 0 to ‘m’ so frequency count is ‘m+1’ for fifth instruction. In instruction five value of ‘j’ is check from 0 to ‘n’ so frequency count is ‘n+1’ but this instruction is in the for loop which execute for ‘m’ times, so for seventh instruction is m*(n+1). Ninth instruction is in the two for loops, out of which first for loop execute for m times and second ‘for’ loop execute for ‘n’ times. So for ninth instruction frequency count is m*n. The total frequency count for the above program is (m+1)+m(n+1)+mn=2m+2mn+1=2m(1+n)+1.

Consider the following example

 Explanation : For above program total frequency count

    = (m+1)+m(n+1)+mn+mn(n+1)+mn

    = m+1+mn+m+mn+mn2 +mn+mn2

    = 2 mn2+3mn+2m+1

    = mn(2n+3)+2m+1

 Consider the following example

 Explanation : the above example, one is add to frequency count for instruction four. The loop will execute till value of n is incremented to 10 from 1, so for loop statements ie instructions seven and eight is execute for tem times. when the value of ‘n’ is ten then ‘break’ statement will execute for one time and it will skip the tenth execution of tenth instruction. Tenth instruction will add value nine to frequency count. Total frequency count for above program is 10+10+1+9+10 = 40.

To express the running time complexity of algorithm three asymptotic notations are available. Asymptotic notations are also called as asymptotic bounds. Notations are used to relate the growth of complex function with the simple function. Asymptotic notations have domain of natural numbers. These notations are as follows

 1. Big-oh notation : Big-oh notations can be express by using ‘o’ symbol. This notation indicates the maximum number of steps required to solve the problem. This notation expresses the worst case growth of an algorithm. Consider the following diagram in which there are two functions f(x) and g(x). f(x) is more complex than the function g(x).

Fig. 3.7

 In the above diagram out of two function f(n) and g(n), more complex function is f(n), so need to relate its growth as compare to simple function g(n). More specifically we need one constant function c(n) which bound function f(n) at some point n0. Beyond the point ‘n0’ function c*g(n) is always greater than f(n).

 Now f(n)=Og(n)if there is some constant ‘c’ and some initial value ‘n0’. such that f(n)<=c*g(n) for all n>n0

 In the above expression ‘n’ represents the input size

 f(n) represents the time that algorithm will take

 f(n) and g(n) are non-negative functions.

 Consider the following example

Fig. 3.8

 In the above example g(n) is ‘’n’ and f(n) is ‘2n+1’ and value of constant is 3. The point where c*g(n) and f(n) intersect is ‘’n0’. Beyond ‘n0’ c*g(n) is always greater than f(n) for constant ‘3’. We can write the conclusion as follows

 f(n)=O g(n)    for constant ‘c’ =3 and ‘n0’=1

 such that f(n)<=c*g(n) for all n>n0

 2. Big-omega notation : Big-omega notations can be express by using ‘Ω’ symbol. This notation indicates the minimum number of steps required to solve the problem. This notation expresses the best case growth of an algorithm. Consider the following diagram in which there are two functions f(n) and g(n). f(n) is more complex than the function g(n).

Fig. 3.9

 In the above diagram out of two function f(n) and g(n), more complex function is f(n), so need to relate its growth as compare to simple function g(n). More specifically we need one constant function c(n) which bound function f(n) at some point n0. Beyond the point ‘n0’ function c*g(n) is always smaller than f(n).

 Now f(n)=Ωg(n)if there is some constant ‘c’ and some initial value ‘n0’. such that c*g(n) <= f(n)for all n>n0

 In the above expression ‘n’ represents the input size

 f(n) represents the time that algorithm will take

 f(n) and g(n) are non-negative functions.

 Consider the following example

 In the above example g(n) is ‘2n’ and f(n) is ‘2n-2’ and value of constant is 0.5. The point where c*g(n) and f(n) intersect is ‘’n0’. Beyond ‘n0’ c*g(n) is always smaller than f(n) for constant ‘0.5’. We can write the conclusion as follows

 f(n) = Ω g(n)    for constant ‘c’ =0.5 and ‘n0’=2

 such that  c*g(n)<= f(n) for all n>n0

Fig. 3.10

 Big-theta notation : Big-theta notations can be express by using ‘Ɵ’ symbol. This notation indicates the exact number of steps required to solve the problem. This notation expresses the average case growth of an algorithm. Consider the following diagram in which there are two functions f(n) and g(n). f(n) is more complex than the function g(n).

Fig. 3.11

 In the above diagram out of two function f(n) and g(n), more complex function is f(n), so need to relate its growth as compare to simple function g(n). More specifically we need one constant function c1 and c2 which bound function f(n) at some point n0. Beyond the point ‘n0’ function c1*g(n) is always smaller than f(n) and c2*g(n) is always greater than f(n).

 Now f(n) =  g(n) if there is some constant ‘c1 and c2’ and some initial value ‘n0’. such that c1*g(n) <= f(n)<=c2*g(n)for all n>n0

 In the above expression ‘n’ represents the input size

 f(n) represents the time that algorithm will take

 f(n) and g(n) are non-negative functions.

 f(n) =  g(n) if and only if f(n)=O g(n) and f(n)=Ω g(n)

 Consider the following example

Fig. 3.12

 In the above example g(n) is ‘2n’ and f(n) is ‘3n-2’ and value of constant c1 is 0.5 and c2 is 2. The point where c*g(n) and f(n) intersect is ‘’n0’. Beyond ‘n0’ c1*g(n) is always smaller than f(n) for constant ‘0.5’ and c2*g(n) is always greater than f(n) for constant ‘2’. We can write the conclusion as follows

 f(n)=Ω g(n)    for constant ‘c1’ =0.5 , ‘c2’ = 2 and ‘n0’=2

 such that  c1*g(n)<= f(n)<=c2*g(n) for all n>n0

2.2 Searching methods: Linear, Binary and Fibonacci Search.

Given a collection of objects, the goal of search is to find a particular object in this collection. The objects have key values on which search is performed and data values which correspond to the information one wishes to retrieve once an object is found. For example, a telephone book is a collection of names on which one searches and telephone numbers which correspond to the data being sought. The collection of objects is often stored in a list or an array. Given a collection of objects in an array A[1.. n], the ith  element A[i] corresponds to the key value of the ith  object in the collection. The input to a search algorithm is an array of objects A, the number of objects n, and the key value being sought x.

 Thus Algorithm for Linear Search is

 1. start at one end of the list

 2. if the current element is not equal to the search target, move to the next element,

 3. stop when a match is found or the opposite end of the list is reached.

 Function for Linear search is

 If element is found this function returns index of that element otherwise it returns –1.

Example : we have an array of integers, like the following:

 Let’s search for the number 7. According to function for linear search index for element 7 should be returned. We start at the beginning and check the first element in the array.

 First element is 9.Match is not found and hence we move to next element i.e 6.

 Again match is not found so move to next element i.e.7.

 We found the match at the index position 2. Hence output is 2.

 If we try to find element 10 in above array, it will return –1,as 10 is not present in the array.

Complexity Analysis of Linear Search:

 Let us assume element x is to be searched in array A of size n.

 An algorithm can be analyzed using following three cases.

 1. Worst case

 2. Average case

 3. Best case

 1. Worst case : In Linear search worst case happens when element to be searched is not present. When x is not present, the linear search function compares it with all the elements of A one by one. The size of A is n and hence x is to be compared with all n elements. Thus, the worst case time complexity of linear search would be O(n).

 2. Average case : In average case analysis, we take all possible inputs and calculate computing time for all of the inputs. Sum all the calculated values and divide the sum by total number of inputs. Following is the value of average case time complexity.

   Average Case Time = (((=  ((((

    = O (n)

 3. Best Case : In linear search , the best case occurs when x is present at the first location. So time complexity in the best case would be O(1).

Merits :

 1. Simple and easy to implement

 2. It works well even on unsorted arrays.

 3. It is memory efficient as it does not require copying and partitioning of the array being searched.

Demerits :

Suitable only for small number of values.

It is slow as compared to binary search.

 Binary Search requires sorted array.

 Steps to perform binary search on sorted array A of size n are as follows.

 1. Initialize lower and upper limit of array to be searched Low=0,High= n–1.

  2. Find the middle position

  Mid=(Low + High)/2

 3. Compare the input key value with the key value of the middle element of the array. It has 3 possibilities.

Case 1 : If keys match then return mid and print element found.

Case 2 : If key is less than middle element then element is present in left half of array. Update High and goto step 2. 

Case 3 : If key is greater than middle element then element is present in right half of array. Update Low and goto step 2. 

Case 4: if(Low>High)

Example 1 : Let array A= {–1, 5, 6, 18, 19, 25, 46, 78, 102, 114}. We want to find element ‘6’ using binary search.

Solution:

 Step 1 : Low=0, High= 9

 Step 2 : Mid=(Low + High)/2

 Mid = (0+9)/2 =4.5 i.e 4. It means middle element is located at position 4. So A[Mid] is 19.Thus

 Low=0

 Mid=4

 High=9   

 Step 3 : Compare 6 with 19. It satisfies case 2 of step 3. so High= 4–1=3 and element is present in left half of array. We can ignore right half of array.

 Repeat step 2. So mid= (0+3)/2 = 1.5 i.e 1. mid is at position 1. Element 5 is present at position 1.

 Low = 0

 Mid = 1

 High = 3

 Again compare 5 with 6. It satisfies case 3 of step 3. so

 Low = 1+1=2.  

 Repeat step 2. Mid= (2+ 3)/2= 2.5 i.e 2 .Mid is at position 2. Element 6 is at position 2.

 Low=2

 Mid=2

 High=3  

 Compare 6 with 6.

 Match is found. Return the position and print element found.

Example 2 : Find 103 in {–1, 5, 6, 18, 19, 25, 46, 78, 102, 114} using Binary Search.

Step 1 : Low=0

High=9

Step 2 : Mid=(0+9)/2=4

 So middle element is 19.

Step 3 : Compare(103,19)

 103>19 hence element is located at right half of array and we can ignore left half of array. Update Low and recalculate mid.

    Low = 4+1=5

    High = 9 

    Mid = (5+9)/2=7

 Middle element is 78. Compare(103,78)

 103>78. Recalculate Low and Mid

    Low = 7+1=8

    High = 9

    Mid = (8+9)/2=8

 Middle element is 102. Compare(103,102)

 103>102. Recalculate Low and Mid.

    Low = 8+1=9

    High = 9

 Here Low=High and match is not found hence we conclude that element is not present in array.

Example 3 : Find 44 in A={5,12,17,23,38,44,77,84,90} using binary search.

Step 1: Low=0

  High=8

  Mid=(0+8)/2=4

 Middle element is 38. Compare(44,38)

 44>38.Thus element is located at right half of array and we can ignore left half of array. Recalculate Low and Mid.

    Low = (4+1)= 5

    High = 8

    Mid = (5+8)/2=6.5 i.e 6

 Middle element is 77. Compare(44,77)

 44<77. Recalculate High and Mid.

 Low=5

    High = 6–1=5

    Mid = (5+5)/2=5

 Middle element is 44. Compare(44,44)

 Match is Found. Return index and print “Element Found.”

 Algorithm for Recursive Binary Search

Complexity Analysis of Binary Search : 

 Assume our array size is 16.

 When n= 16 BinarySearch is called to reduce size to n=8.

 When n= 8 BinarySearch is called to reduce size to n=4.

 When n= 4 BinarySearch is called to reduce size to n=2.

 When n= 2 BinarySearch is called to reduce size to n=1 .

 Thus we see that BinarySearch function is called 4 times

 i.e. 4 elements of the array were examined for n =16.

 Note that 16 = 24

 Let us consider a more general case where

 n is still a power of 2. Let us say n =2k

 After k searches, the while loop is executed k times and n reduces to size 1. Let us assume that each run of the while loop involves at most 4 operations.

 Thus total number of operations: 4k.

 The value of k can be determined from the expression

    2k = n

 Taking log of both sides

    k = log n

 Thus total number of operations = 4 log n.

 We conclude that the time complexity of the Binary search method is O(log n), which is much more efficient than the Linear Search method.

Merits :

 Binary Search is fast and efficient.

 Suitable for large number of values.

Demerits :

 Binary search works only on sorted array or list.

Fibonacci series generates the subsequent number by adding two previous numbers. Fibonacci series starts from two numbers − F0 & F1. The initial values of F0 & F1 can be taken 0, 1 or 1, 1 respectively.

Fibonacci series satisfies the following conditions −

Fn = Fn-1 + Fn-2

Hence, a Fibonacci series can look like this −

F8 = 0 1 1 2 3 5 8 13

or, this −

F8 = 1 1 2 3 5 8 13 21

Fibonacci Iterative Algorithm

First we try to draft the iterative algorithm for Fibonacci series.

Procedure Fibonacci(n)

   declare f0, f1, fib, loop

   set f0 to 0

   set f1 to 1

   display f0, f1

   for loop ← 1 to n

      fib ← f0 + f1  

      f0 ← f1

      f1 ← fib

      display fib

   end for

end procedure

Fibonacci Recursive Algorithm

Let us learn how to create a recursive algorithm Fibonacci series. The base criteria of recursion.

START

Procedure Fibonacci(n)

   declare f0, f1, fib, loop

   set f0 to 0

   set f1 to 1

   display f0, f1

   for loop ← 1 to n

      fib ← f0 + f1  

      f0 ← f1

      f1 ← fib

      display fib

   end for

END

2.3 Sorting methods: Bubble, Insertion, Selection, Merge, and Quick Sort.

Steps to perform Bubble sort are as follows.

Assume we want to sort the elements in ascending order and no two elements are equal.

 1. Compare first element with second element. If first element is greater than next element, we interchange their position accordingly. i.e first element is moved to second element’s position and second element is moved to first element’s position. If No, then we don’t interchange any elements. 

 2. The element in second position is compared with element in third position and the process of interchanging elements is performed if second is greater than third element. The whole process of comparing and interchanging is repeated till last element. When the process gets completed, the largest element in array will get placed in the last position of the array.

 Let us consider array A of size n. Then Algorithm for Bubble sort is

 1. Set i to 0.

 2. Set j to 0.

 3. if(A[j]>A[j+1])

  swap A[j],A[j+1]

 4. Increment j

 5. if j<(n–1–i) goto step 3

 6. Increment i

 7. if(i<n–1) goto step  2.

Example 1 : Suppose the following numbers are stored in an array A:

 We apply bubble sort to array A. We discuss each pass separately.

Pass 1

 1. Compare j[0] and j[1]. Since 32 < 51, the list is not altered.

 2. Compare j[1] and j[2] Since 51 > 27, interchange 51 and 27 as follows:

 Array A becomes

 3. Compare j[2] and j[3]. Since 51 < 85, array is not altered.

 4. Compare j[3] and j[4]. Since 85 > 66, interchange 85 and 66 as follows:

 Array A becomes

 5. Compare j[4] and j[5]. Since 85 > 23, interchange 85 and 23 as follows:

 Array A becomes

 6. Compare j[5] and j[6]. Since 85 > 13, interchange 85 and 13 as follows:

 7. Compare j[6] and j[7]. Since 85 > 57, interchange 85 and 57 as follows:

 Array A becomes

 At the end of this first pass, the largest number, 85, has moved to the last position. However, the rest of the numbers are not sorted, even though some of them have changed their positions.

 Pass 2 will move second last number at second last position, Pass 3 will move third last number at third last position and so on. Here we show array after every pass.

Pass 2 :

Pass 3 :

Pass 4:

Pass 5 :

Pass 6 :

 Hence the array is sorted in 6 passes.

 We will see one more example

Example 2 : Apply Bubble Sort on array A= {5,3,1,9,8,2,4,7}. 

Pass 2 : i=2 

Pass 3 :

Pass 4 :

 This array gets sorted in 4 passes only.

Example : Apply Bubble Sort on array A= {23,78,45,8,32,56}

Pass 1 :

Pass 2 :

Pass 3 :

 This array is sorted in 3 passes.

Complexity Bubble sort:

 Suppose we have a list with n elements, and each element perform n – 1 comparisons with elements to its left, and swap, if necessary.

 Best Case: If the list is already sorted, only one iteration is performed  and complexity is O(1).

 Average and Worst case: For n elements at most n – 1 swap operations is performed in each pass. The worst and average case complexity is O(n2).

Insertion Sort reads all elements from 1 to n and inserts each element at its proper position. This sorting method works well on small list of elements. 

 Procedure for each pass is as follows.

Pass 1 :

 A[l] by itself is trivially sorted.

Pass 2 :

 A[2] is inserted either before or after A[l] so that: A[l], A[2] is sorted.

Pass 3 :

 A[3] is inserted into its proper place so that: A[l], A[2], A[3] is sorted.

Pass 4 :

 A[4] is inserted into its proper place A[l], A[2], A[3], A[4] is sorted.

Pass N :

 A[N] is inserted into its proper place in  so that:

 A[l], A[ 2 ] , . . . , A[ N ] is sorted

Example : We will apply insertion sort on original list of Fig.3.Assume we are arranging elements in ascending order.

Fig.: Original List

Pass 1 :

Hence the list is sorted using insertion sort.

We will see one more example.

 Apply Insertion sort on array A= {77,30,40,10,88,20,65,56}

After Pass 4

After Pass 8

Hence the list is sorted using Insertion sort.

Output  :

 Enter number of elements

 5

 Enter 5 integers

 9

 4

 2

 5

 3

 Sorted  list in ascending order

 2

 3

 4

 5

 9

Complexity of Insertion Sort :

 Worst Case Complexity: In the worst case, for each i we do (i – 1) swaps inside the inner for–loop–therefore, overall number of swaps (when i goes from 2 to n in the outer for loop) is

    T(n) = 1 + 2 + 3 +...+(I – 1) +....+ n – 1

     = n  (n – 1)/2

     = O(n2)

 Average case Complexity is O(n2).

 Best Case Complexity is O(n).

Assume we want to sort list in ascending order. Selection sort finds the smallest element from unsorted list and swap it with the element in first position. Then it finds second smallest element and swap it with element at second position. This process is repeated till entire list is sorted in ascending order. Each time we swap elements,  we say that we  have completed a sort pass. A list of  n elements requires  n–1 passes to completely  rearrange the data.

 Procedure for every pass is as follows.

 Pass 1 : Find the position P of the smallest in the list of N elements A[l], A[2], . . . , A[N], and then interchange A[P] and A[1] . Then A[1] is sorted.

 Pass 2 : Find the position P of the smallest in the sublist of N –1 elements A[2], A[3],. . . , A[N], and then interchange A[P]and A[2]. Then A[l], A[2] is sorted.

 Pass 3 : Find the position P of the smallest in the sublist of N–2  elements A[3], A[4], . . . , A[N], and then interchange A[P] and A[3]. Then: A[l], A[2] , A[3] is sorted.

 Pass N –1 : Find the position P of the smaller of the elements A[N –1), A[N], and then interchange A[P] and A[N–1]. Then: A[l], A[2], . . . , A[N] is sorted. Thus A is sorted after N –1 passes.

Example 1 :      

Fig.: Original List

 We will apply selection sort on this list.

After Pass 2 :

We will see one more example.

Apply selection sort on array A= {77,30,40,10,88,20,65,56}

After Pass 6

 Hence the list is sorted in ascending order by applying selection sort.

Output:

 Enter number of elements

 5

 Enter 5 integers

 4

 1

 7

 5

 9

 Sorted list in ascending order

 1

 4

 5

 7

 9

Complexity of Selection Sort :

 In selection sort outer for loop is executed n–1 time. On the kth time through the outer loop, initially the sorted list holds

 k–1 elements and unsorted portion holds n–k+1 element.  In inner for loop 2 elements are compared each time.

 Thus, 2*(n–k) elements are examined by the inner loop during the k th pass through the outer loop. But k ranges from 1 to n–1.

 Total number of elements examined is:

    T(n) = 2*(n –1) + 2*(n–2) + 2*(n–3) + .. + 2*(n–(n–2))

     + 2*(n–(n–1))

    = 2*((n–1) + (n–2) + (n–3) + ... + 2 + 1)

 (or 2*(sum of first n–1 integers)

    = 2*((n–1)*n)/2)

    = n2 – n, so complexity of algorithm is O(n2).

Merge Sort is based on divide and conquer strategy. It divides the unsorted list into n sublists such that each sublist contains one element. Each sublist is then sorted and merged until there is only one sublist.

 Step 1 : Divide the list into sublists such that each sublist contains only one element.

 Step 2 : Sort each sublist and Merge them.

 Step 3 : Repeat Step 2 till the entire list is sorted.

Example : Apply Merge Sort on array A= {85,24,63,45,17,31,96,50}

 Step1 : A contains 8 elements. First we divide the list into two sublists such that each sublist contains 4 elements. Then we divide each sublist of 4 elements into sublist of two elements each. Finally every sublist contains only one element.

Fig. 4.4

 Step 2 : Now we start from bottom. Compare 1st and 2nd element. Sort and merge them. Apply this for all bottom elements.

 Thus we got 4 sublists as follows

 Step 3 : Repeat this sorting and merging until entire list is sorted. Thus above four sublists are sorted and merged to form 2 sublists.

 Finally above 2 sublists are again sorted and merged in one sublist.

 We will see one more example on merge sort.

Example : Apply merge Sort on array A={10,5,7,6,1,4,8,3,2,9,12,11}

Step 1 :

Fig. 4.5

Algorithm for Merge Sort:

 Let    x = no. of elements in array A

    y = no. of elements in array B

    C = sorted array with no. of elements n

    n = x+y

Following algorithm merges a sorted x element array A and sorted y element array B into a sorted array C, with n = x + y elements. We must always keep track of the locations of the smallest element of A and the smallest element of B which have not yet been placed in C. Let LA and LB denote these locations, respectively. Also, let LC denote the location in C to be filled. Thus, initially, we set

 LA : = 1,

 LB : = 1 and

 LC : = 1.

 At each step , we compare A[LA] and B[LB] and assign the smaller element to C[LC].

 Then 

 LC:= LC + 1,

 LA: = LA + 1, if new element has come from A .

 LB: = LB + 1, if new element has come from B.

 Furthermore, if LA> x, then the remaining elements of B are assigned to C; 

 LB >y, then the remaining elements of A are assigned to C.

 Thus the algorithm becomes

 MERGING ( A, x, B, y, C)

 1. [Initialize ] Set LA : = 1 , LB := 1 AND LC : = 1

 2. [Compare] Repeat while LA <= x and LB <= y

 If A[LA] < B[LB] , then

 (a) [Assign element from A to C ] set C[LC] = A[LA]

 (b) [Update pointers ] Set LC := LC +1 and LA = LA+1

 Else

 (a) [Assign element from B to C] Set C[LC] = B[LB]

 (b) [Update Pointers] Set LC := LC +1 and LB = LB +1

 [End of loop]

 3. [Assign remaining elements to C]

 If LA > x , then

 Repeat for K= 0 ,1,2,........,y–LB

 Set C[LC+K] = B[LB+K]

 [End of loop]

 Else

 Repeat for K = 0,1,2,......,x–LA

 Set C[LC+K] = A[LA+K]

 [End of loop]

 4. Exit

Output :

 Enter the total number of elements: 5

 Enter the elements which to be sort: 3 1 6 4 7

 After merge sorting elements are: 1 3 4 6 7

Complexity of Merge Sort :

 Time to merge sort N elements = Time to merge sort N/2 elements plus time to merge two arrays each N/2 elements.

 Time to merge two arrays each N/2 elements is linear, i.e. N

 Thus we have:

 (1) T(1) = 1

 (2) T(N) = 2T(N/2) + N

 Dividing (2) by N we get:

 (3) T(N) / N = T(N/2) / (N/2) + 1

 N is a power of two, so we can write

 (4) T(N/2) / (N/2) = T(N/4) / (N/4) +1

 (5) T(N/4) / (N/4) = T(N/8) / (N/8) +1

 (6) T(N/8) / (N/8) = T(N/16) / (N/16) +1

 (7) ……
 (8) T(2) / 2 = T(1) / 1 + 1

Adding equations (3) through (8), the sum of their left–hand sides will be equal to the sum of their right–hand sides:

T(N) / N + T(N/2) / (N/2) + T(N/4) / (N/4) + … + T(2)/2

= T(N/2) / (N/2) + T(N/4) / (N/4) + ….+ T(2) / 2 + T(1) / 1 + LogN

(LogN is the sum of 1s in the right–hand sides)

 After crossing the equal term, we get

 (9) T(N)/N =  T(1)/1 + LogN

 T(1) is 1, hence we obtain

(10) T(N) = N + NlogN = O(NlogN)

 Hence the complexity of the Merge Sort algorithm is O(NlogN).

 Quick sort is most efficient method of sorting .It uses divide and conquer strategy to sort the elements. In quicksort, we divide the array of items to be sorted into two partitions and then call the quicksort procedure recursively to sort the two partitions. For this we choose a pivot element and arrange all elements such that all the elements in the left part are less than the pivot and all those in the right part are greater than it.

Algorithm to implement Quick Sort is as follows.

 Consider array A of size n to be sorted. p is pivot element. Index positions of first and last element of array A is denoted by ‘first’ and ‘last’.

Initially first=0 and last=n–1.

Increment first till A[first]<=p

Decrement last till A[last]>=p

If first < last then swap A[first] with A[last].

If first > last then swap p with A[last] and thus position of p is found. Pivot p is placed such that all elements to its left are less than it and all elements right to it are greater than it. Let us assume that j is final position of p. Then A[0] to A[j–1] are less than p and A [j + 1] to A [n–1]are greater than p.

Now we consider left part of array A i.e A[0] to A[j–1].Repeat step 1,2,3 and 4. Apply same procedure for right part of array.

We continue with above steps till no more partitions can be made for every subarray.

 We will see examples on Quick sort

Example : Apply Quicksort on array

 A= {27,6,39,2,65,12,57,18,49,19}

Pass 1 :

Here again first<last so we swap A[first] and A[last]. Swapping 65 and 18 we get

Here we complete Pass 1.Now pivot element is 27 and it divides array in left and right partition. We can see that elements less than pivot are in left partition and elements greater than pivot are in right partition.

Now we continue same procedure for left and right partition.  Here we see results of corresponding passes.

Pass 2 :

Pass 3 :

Pass 4 :

Pass 5 :

Pass 6 :

Pass 7 :

 We will see another example.

Example : Apply Quicksort on array A={21,55,49,38,13,93,87,9}

Now first>last hence swap pivot and A[last].Swapping 21 and 13 we get

Now first > last hence swap pivot and A [last]’. Swapping 21 and 13 we get

Left Partition

Hence the left partition is sorted.

Considering right partition