Unit-2-Linear Data Structure, Searching, Sorting.pptx

Breif

1. . “Linear Data Structure using Searching and Sorting” Prof. Shravani m. k Comp Dept. SKNCOE Unit-II

2. Overview of Array, Array as an Abstract Data Type, Operations on Array, Storage Representation, Multidimensional Arrays[2D, nD ], Sparse matrix representation using 2D Searching: Sequential Search/Linear Search, Binary Search, Fibonacci Search, and Indexed Sequential Search. Sorting: Concepts- Stability, Efficiency, and Number of Passes, Internal and External Sorting, Bubble sort, Insertion Sort, Selection Sort , Quick Sort, Merge sort Case Study : Social Network Adjacency Matrix Representing friendship connections among millions of users.

3. SEQUENTIAL ORGANIZATION Definition : “ In computer science, sequential access means that a group of elements (such as data in a memory array or a disk file or on magnetic tape data storage) is accessed in a predetermined, ordered sequence. Sequential access is sometimes the only way of accessing the data , for example if it is on a tape .” 3

4. Linear Data Structure Using Sequential Organization 4 Definition : “The data structure where data items are organized sequentially or linearly one after another is called as Linear Data Structure ” A linear data structure traverses the data elements sequentially, in which only one data element can directly be reached. Ex: Arrays, Linked Lists.

5. Array 4 Definition : “ An array is a finite ordered collection of homogeneous data elements which provides direct access (or random access) to any of its elements. An array as a data structure is defined as a set of pairs (index,value) such that with each index a value is associated. index — indicates the location of an element in an array. value - indicates the actual value of that data element. Declaration of an array in ‘C++’: int Array_A[20]; ”

6. Array Array Representation Arrays can be declared in various ways in different languages. For illustration, let's take C array declaration. Arrays can be declared in various ways in different languages. For illustration, let's take C array declaration. As per the above illustration, following are the important points to be considered . 6

7. Array 7 Array Representation Index starts with 0. Array length is 10 which means it can store 10 elements. Each element can be accessed via its index. For example, we can fetch an element at index 6 as 9. Basic Operations Following are the basic operations supported by an array. Traverse − print all the array elements one by one. Insertion − Adds an element at the given index. Deletion − Deletes an element at the given index. Search − Searches an element using the given index or by the value. Update − Updates an element at the given index.

8. Characteristics of array 8 An array is a finite ordered collection of homogeneous data elements. In array, successive elements of list are stored at a fixed distance apart. Array is defined as set of pairs-( index and value). Array allows random access to any element deletion of element in In array, insertion and between positions requires data movement. static allocation, which means space once during compile time, can not be Array provides allocation done changed run time.

9. Advantage of Array Data Structure 9 56 Arrays permit efficient random access in constant time 0(1). Arrays are most appropriate for storing a fixed amount of data and also for high frequency of data retrievals as data can be accessed directly. Wherever there is a direct mapping between the elements and there positions, arrays are the most suitable data structures. Ordered lists such as polynomials are most efficiently handled using arrays. Arrays are useful to form the basis for several more complex data structures, such as heaps, and hash tables and can be used to represent strings, stacks and queues.

10. Disadvantage of Array Data Structure 10 56 Arrays provide static memory management. Hence during execution the size can neither be grown nor shrunk. Array is inefficient when often data is to inserted or deleted as inserting and deleting an element in array needs a lot of data movement. Hence array is inefficient for the applications, which very often need insert and delete operations in between.

11. Applications of Arrays 11 56 Although useful in their own right, arrays also form the basis for several more complex data structures, such as heaps, hash tables and can be used to represent strings, stacks and queues. All these applications benefit from the compactness and direct access benefits of arrays. Two-dimensional data when represented as Matrix and matrix operations.

12. X(Base ) X+1 7 Fig 2.1 Memory Representation Memory Representation and Calculation 7

13. The address of the i th element is calculated by the following formula (Base address) + (offset of the i th element from base address) Here, base address is the address of the first element where array storage starts. ADDRESS CALCULATION 2

14. Arrays are stored in consecutive set of memory locations. Array can be thought of as set of index and values. For each index which is defined there is a value associated with that index. There are two operations permitted on array data structure .retrieve and store ADT for an array

15. CREATE()-produces empty array. RETRIVE(array,index)->value Takes as input array and index and either returns appropriate value or an error. STORE(array,index,value)-array used to enter new index value pairs. ADT for an array

16. Representation and analysis Type variable_name[size] Operations with arrays: Copy Insert Delete Search Sort Merging of sorting arrays. Introduction to arrays

17. ADT is written with the help of instances and operations Formally ADT is a collection of domain, operations, and axioms (or rules) For defining an array as an ADT, we have to define its very basic operations or functions that can be performed on it The basic operations of arrays are creation of an array, storing an element, accessing an element, and traversing the array 2 6 ARRAY AS AN ADT 26

18. List of operation on Array :- 1 . Inserting an element into an array 2. deleting element from array 3. searching an element from array 4. sorting the array element 18

19. # a = [1, 2, 3] b = a.copy () # Method 1 c = a[:] # Method 2 d = list(a) # Method 3 print("Original:", a) print("Copy1:", b) print("Copy2:", c) print("Copy3:", d) 🖥 Output: Original: [1, 2, 3] Copy1: [1, 2, 3] Copy2: [1, 2, 3] Copy3: [1, 2, 3] Copy o perations on array:

20. a = [10, 20, 30] This creates a list named a with 3 elements: 10, 20, and 30. b = a.copy () # Copy array This creates a copy of the list a and stores it in a new variable b. a.copy () creates a shallow copy — meaning b is a new list with the same elements, but stored separately. Changes to b will not affect a, and vice versa. print("Original:", a) Prints the original list a. print("Copied:", b) Prints the copied list b. Output: Original: [10, 20, 30] Copied: [10, 20, 30] Even though both lists look the same, they are stored separately in memory.

21. Insertion o peration on array: a = [10, 20, 30] a.insert (1, 15) # Insert 15 at index 1 print(a) Output: [10, 15, 20, 30]

22. a = [10, 20, 30] This creates a list (array) named a with three elements: 10, 20, and 30. a.insert (1, 15) This inserts the number 15 at index 1 (the second position). After insertion, the list becomes: [10, 15, 20, 30] All elements from index 1 onward are shifted right to make space. print(a) Prints the updated list: [10, 15, 20, 30] 🔁 General Syntax: list.insert (index, value)

23. To Remove A Given Number From The Array. a = [10, 20, 30, 40] a.remove (30) # Removes the first occurrence of 30 print(a) Output: [10, 20, 40]

24. a = [10, 20, 30, 40] This creates a list a with four numbers: 10, 20, 30, and 40. a.remove (30) This removes the first occurrence of the value 30 from the list. After removal, the list becomes: [10, 20, 40]. print(a) This prints the updated list: [10, 20, 40] Important Notes: remove(value) removes the value, not by index. If the value doesn't exist in the list, Python will raise an error .

25. REVERSE Operation on Array a = [10, 20, 30] a.reverse () print(a) Output: [30, 20, 10] Alternate (using slicing): a = [10, 20, 30] print(a[::-1]) Both methods reverse the array — the first one modifies the original list, the second one creates a reversed copy.

26. a = [10, 20, 30] a.reverse () print(a) What it does: a.reverse () reverses the list in place. It modifies the original list. After reversal: a becomes [30, 20, 10]. 🔹 2. Using slicing [::-1] a = [10, 20, 30] print(a[::-1]) What it does: a[::-1] creates a new reversed list using slicing. [::-1] means: Start from the end (-1 step) Go backward through the list The original list a is not changed. Output (both): [30, 20, 10]

27. One-Dimensional Array A one-dimensional array is a collection of elements (usually of the same data type) that are stored in a single row or linear form , and can be accessed using an index . A one-dimensional array is like a list of items placed in a straight line , where each item has a position number (index) . Key Points It holds elements in a single row (i.e., one dimension). Each element is accessed using an index , starting from 0. The size of the array is fixed when created .

28. # Creating a one-dimensional array (using list in Python) marks = [78, 85, 90, 66, 72] # Accessing elements print(marks[0]) # Output: 78 print(marks[3]) # Output: 66 # Changing value at index 2 marks[2] = 95 # Printing entire array print(marks) # Output: [78, 85, 95, 66, 72] Memory Layout Stored in contiguous memory locations . Example: marks = [78, 85, 95, 66, 72] Indexes: 0 1 2 3 4

29. Derive address calculation formula for a one-dimensional array with one example To access an element in an array stored in memory, we use a formula to calculate the memory address of any element. General Formula If: Base = Base address of the array in memory W = Size (in bytes) of each element i = Index of the element to access A[ i ] = ith element of array A Address of A[ i ]: Address of A[ i ]=Base+( i×W ) Example Let’s say: Array: A[5] = [10, 20, 30, 40, 50] Base address = 1000 Each element size = 4 bytes (e.g., integer) Find address of A[3]

30. Index Value Address A[0] 10 1000 A[1] 20 1004 A[2] 30 1008 A[3] 40 1012 A[4] 50 1016 Calculation Address of A[3]=1000+(3×4)=1000+12=1012​ So, the memory address of A[3] is 1012 . Memory Layout

31. Two-dimensional Arrays A two dimensional array is multidimensional array and it is the arrangement of elements in rows and columns It has two indices, one for row and other for column. First index represents the number of rows, second index represents the number of columns arrayName [ x ][ y ];

32. 2D ARRAY IN PROGRAMMING Ques: Accept & Display a 3*3 Matrix. # Accepting a 3x3 matrix from the user matrix = [] print("Enter elements for a 3x3 matrix:") for i in range(3): row = [] for j in range(3): val = int(input( f"Enter element at position ({i+1},{j+1}): ")) row.append ( val ) matrix.append (row) # Displaying the matrix print("\ nThe 3x3 matrix is:") for row in matrix: print(row) Enter elements for a 3x3 matrix: Enter element at position (1,1): 1(1 st row,1 st value) Enter element at position (1,2): 2(1 st row, 2 nd value) Enter element at position (1,3): 3 Enter element at position (2,1): 4 Enter element at position (2,2): 5 Enter element at position (2,3): 6 Enter element at position (3,1): 7 Enter element at position (3,2): 8 Enter element at position (3,3): 9 The 3x3 matrix is: [1, 2, 3] [4, 5, 6] [7, 8, 9]

33. Columns Col1 col2 .... coln A00 A01 .... A0n A10 A11 .... A1n : : : Am0 Am1 .... Amn m*n Rows R0 R1 1 2 3 4 5 6 7 8 34 9 11 12 Matrix M = Row-major Representation Column-major Representation

34. Row-major representation 35 mxn matrix 4x3

35. 1. Row-Major Representation: Address of A [i][j] = Base Address + [(i * n ) + j]*element size 2. Column-Major Representation: Address of A [i][j] = Base Address + [(j * m ) +i]* element size

36. Row-major representation 37 In row-major representation, the elements of Matrix are stored row-wise, i.e., elements of 1st row, 2nd row, 3rd row, and so on till m th row 1 2 3 4 5 6 7 8 9 10 11 12 (0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3) Row1 Row2 Row3

37. Row major arrangement Row 0 Row 1 Row m-1 Row 0 Row 1 Row m-1 Row-major arrangement in memory , in row major representation 38

38. Column-major representation PROF. ANAND GHARU 39 In column-major representation m × n elements of two- dimensional array A are stored as one single row of columns. The elements are stored in the memory as a sequence as first the elements of column 1, then elements of column 2 and so on till elements of column n

39. Column-major arrangement col1 col2 Col n-1 Col Col 1 Col 2 Memory Location Column-major arrangement in memory , in column major representation 40

40. Example 2.1: Consider an integer array, int A[3][4] . If the base address is 1050, find the address of the element A[2] [3] with row-major and column-major representation of the array. lower bound of index is 0 and we have m=3, n=4, and Base= 1050. Let us compute address of element A [2][3] using the address computation formula 1. Row-Major Representation: Address of A [2][3] = Base + [( i * n ) + j]*element size = 1050 + [(2 * 4) + 3]*2 = 1072 41

41. 1 2 3 4 5 6 7 8 9 10 11 12 (0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3) Row1 Row2 Row3 42 Row-Major Representation of 2-D array

42. 2 . Column-Major Representation: Address of A [2][3] = Base Address + [(j * m ) +i]*2 = 1050 + [(3 * 3) + 2]*2 = 1050 + 22 = 1072 Here the address of the element is same because it is the last member of last row and last column. 43

43. 1 2 3 4 5 6 7 8 9 10 11 12 (0,0) (1,0) (2,0) (0,1) (1,1) (2,1) (0,2) (1,2) (2,2) (0,3) (1,3) (2,3) Col 1 Col 2 Col 3 Col 4 44 Column-Major Representation of 2-D array

44. What is a Sparse Matrix? A sparse matrix is a two-dimensional matrix (or array) that contains mostly zero elements. 45 56 A matrix is called sparse if the number of non-zero elements is significantly less than the number of zero elements . Example: Regular Matrix: 0 0 0 5 0 8 0 0 0 0 3 0 Only 3 values are non-zero → rest are zeros.

45. Characteristics of Sparse Matrix: Only a few values are non-zero Useful for saving memory and time in computation Common in: Graph representations (adjacency matrices) Machine learning (e.g. TF-IDF matrices) Scientific computing (finite element matrices) Most of the values are 0 Why Use Sparse Matrix? ✅ Memory Efficient : Stores only non-zero elements ✅ Faster Processing : Skips unnecessary zero operations ✅ Reduces Complexity : Especially in large datasets

46. # Convert 2D to Sparse Matrix matrix = [ [0, 0, 5], [0, 8, 0], [0, 0, 0] ] sparse = [] for i in range( len (matrix)): for j in range( len (matrix[0])): if matrix[ i ][j] != 0: sparse.append ([ i , j, matrix[ i ][j]]) print(sparse) ✅ Output: [[0, 2, 5], [1, 1, 8]] This output represents the sparse matrix format (triplet form), where each list contains: Row index Column index Non-zero value [0, 2, 5] → element 5 is at position (0, 2) [1, 1, 8] → element 8 is at position (1, 1) All other elements are zero and not stored .

47. matrix = [ [0, 0, 5], # Row 0 [0, 8, 0], # Row 1 [0, 0, 0] # Row 2 ] sparse = [] # Initialize empty list to store sparse matrix in triplet form for i in range( len (matrix)): # Loop through each row for j in range( len (matrix[0])): # Loop through each column in the row if matrix[ i ][j] != 0: # Check if the element is non-zero sparse.append ([ i , j, matrix[ i ][j]]) # Store row, column, and value print("Sparse Matrix (Triplet Format):") # Print heading for row in sparse: # Loop through sparse matrix list print(row) # Print each triplet [row, col, value] Output:Sparse Matrix (Triplet Format): [0, 2, 5]=0 th row, 2 nd column, value [1, 1, 8]=1 st row, 1 st column, value

48. Introduction Searching : “ Searching is a techniques of finding an element in a given list of elements.” List of element could be represented using an Array Linked list Binary tree B-tree Heap

49. Why do we need searching? Searching is one of the core computer science algorithms. We know that today’s computers store a lot of information. To retrieve this information proficiently we need very efficient searching algorithms. Types of Searching Linear search Binary search Sentinel search

50. Sequential search Binary search Fibonacci search Hashed search Index sequential search 4 SEARCH TECHNIQUES

51. Linear Search The linear search is a sequential search, which uses a loop to step through an array, starting with the first element. It compares each element with the value being searched for, and stops when either the value is found or the end of the array is encountered. If the value being searched is not in the array, the algorithm will unsuccessfully search to the end of the array.

52. Linear Search Since the array elements are stored in linear order searching the element in the linear order make it easy and efficient. The search may be successful or unsuccessfully. That is, if the required element is found them the search is successful other wise it is unsuccessfully .

53. Advantages Linear Search easy to understand. It operates on both sorted and unsorted list It doest not require array to be in order Easy to implement Time complexity O(n)

54. Disadvantages Linear Search Linear search is not efficient when list is large Maximum no. of comparision are N(n Element). Not suitable for large problem. You need to search whole list. Linear search is slower.

55. Linear Search Algorithm Consider an integer type array A with size n. So list of elements from that array are, A[0], A[1], A[2], A[3],………………, A[n-1] Declare and initialize one variable which contains the number to be search in an array A. ( variable key is declared) Start Comparing each element from array A with the key LOOP: A[size] == key Repeat step no 2 while A[size] key if key is found, display the location of element(index+1) or else display message KEY NOT FOUND Terminate the program successfully

56. Linear Search Algorithm Linear Search Algorithm Begin by obtaining the target element from the user. Check if this target matches the first item in the list. If a match is found, immediately announce "Element found!" and end the process. If not, proceed to compare the target with the next item in the sequence. Continue this comparison step-by-step until the target has been checked against every element in the list. If the search reaches the final item without a match, display "Element not found!" and conclude the search.

57. Analysis of Linear Search Complexity of linear search : 1.Best Case = O(1) 2.Average Case = O(n) 3.Worst case = O(n)

58. Binary Search “Binary search is an searching algorithm which is used to find element from the sorted list” Concepts : Algorithm can be applied only on sorted data Mid = ( lower+upper )/2 - formula used to find mid Given element is compared with middle element of the list. If key=mid then element is found Otherwise list divide into two part.(key <mid) (>mid) First to mid-1 or mid+1 to last.

59. Binary Search Concepts : If given element is less than middle element then continue searching in first part (first+mid-1) otherwise searching is second part(mid+1 to last). Repeat above step still element is found.

60. Binary Search Assume that two variables are declared, variable first and last, they denotes beginning and ending indices of the list under consideration respectively. Step 1. Algorithm compares key with middle element from list ( A[middle] == key ), if true go to step 4 or else go to next. Step 2. if key < A[ middle ], search in left half of the list or else go to step 3 Step 3. if key > A[ middle ], search in right half of the list or go to step 1 Step 4. display the position of key else display message “NOT FOUND”

61. Binary Search algorithm binarySearch (array, target): low = 0 high = length of array - 1 while low <= high: mid = (low + high) // 2 if array[mid] == target: return mid // Target found else if array[mid] < target: low = mid + 1 // Search right half else: high = mid - 1 // Search left half return -1 // Target not found

62. Example: Let array = [10, 20, 30, 40, 50, 60] and target = 40 low = 0 , high = 5 , mid = 2 , array[2] = 30 40 > 30 → search in right half low = 3 , high = 5 , mid = 4 , array[4] = 50 40 < 50 → search in left half low = 3 , high = 3 , mid = 3 , array[3] = 40 ✅ Found

63. Advatages Binary Search Binary search is optimal searching algorithms Excellent time efficiency 3.Suitable for large list. 4.Faster because no need to check all element. 5.Most suitable for sorted array 6.It can be search quickly 7.Time complexity O(log n)

64. Disadvatages Binary Search Element must be sorted Need to find mid element Bit more complicated to implement and test 4.It does not support random access. 5.Key element require to compare with middle.

65. Element is searched by scanning the entire list from first element to the last Many times entire list is search Simple to implementation Time complexity is O(n) Less efficient sort First list is divided into two sub-lists. Then middle element is compared with key element and then accordingly left or right sub-list is searched Only sub-list is search Complex to implement, since it involves computation for finding the middle element Time complexity is O(log 2 n) More efficient sort Linear Search Vs Binary Search

66. 17 Binary Search

67. Binary Search 2. Calculate middle = (low + high) / 2. = (0 + 8) / 2 = 4. If 37 == array[middle] return middle Else if 37 < array[middle] Else if 37 > array[middle] high = middle -1 low = middle +1

68. Binary Search Repeat 2. Calculate middle = (low + high) / 2. = (0 + 3) / 2 = 1. If 37 == array[middle] return middle Else if 37 < array[middle] Else if 37 > array[middle] high = middle -1 low = middle +1 9/6/201 7 © Reem Al- Attas

69. Binary Search Repeat 2. Calculate middle = (low + high) / 2. = (2 + 3) / 2 = 2. If 37 == array[middle] return middle Else if 37 < array[middle] Else if 37 > array[middle] high = middle -1 low = middle +1 9/6/201 7 © Reem Al- Attas

70. Binary Search 9/6/201 7 © Reem Al- Attas

71. Binary Search 9/6/201 7 © Reem Al- Attas

72. Binary Search 9/6/201 7 © Reem Al- Attas

73. Binary Search 9/6/201 7 © Reem Al- Attas

74. Binary Search 9/6/201 7 © Reem Al- Attas

75. Binary Search Routine }

76. Binary Search Routine }

77. Fibonacci Search: Fibonacci Search is a comparison-based technique that uses Fibonacci numbers to search an element in a sorted array. Similarities with Binary Search:    Works for sorted arrays A Divide and Conquer Algorithm. O(log(n)) complexity.  

78. Differences with Binary Search :  Fibonacci Search divides given array into unequal parts Binary Search uses a division operator to divide range. Fibonacci Search doesn’t use /, but uses + and -. The division operator may be costly on some CPUs. Fibonacci Search examines relatively closer elements in subsequent steps. So when the input array is big that cannot fit in CPU cache or even in RAM, Fibonacci Search can be useful.

79. Selection sort

80. “Sorting is the process ordering a list of element in either ascending or descending order.” Sorting is the operation of arranging the records of a table according to the key value of each record, or it can be defined as the process of converting an unordered set of elements to an ordered set of elements Sorting is a process of organizing data in a certain order to help retrieve it more efficiently 35 SORTING

81. Any sort algorithm that uses main memory exclusively during the sorting is called as internal sort algorithm Internal Sorting techniques : Bubble sort Selection sort Insertion sort Quick sort Shell sort Heap sort Radix sort Bucket sort 36 INTERNAL SORTING(types)

82. Any sort algorithm that uses external memory, such as tape or disk, during the sorting is called as external sort algorithm Merge sort is used in external sorting EXTERNAL SORTING 99

83. A sorting method is said to be stable if at the end of the method, identical elements occur in the same relative order as in the original unsorted set 1. EXAMPLE : STABILITY OF SORTING 101

84. It is usually an estimate of the number of comparisons and data movement required to sort the data SORT EFFICIENCY 104

85. During the sorted process, the data is traversed many times Each traversal of the data is referred to as a sort pass In addition, the characteristic of a sort pass is the placement of one or more elements in a sorted list PASSES IN SORTING 105

86. Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison-based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in order. This algorithm is not suitable for large data sets as its average and worst case complexity are of Ο(n 2 ) where n is the number of items. How Bubble Sort Works? We take an unsorted array for our example. Bubble sort takes Ο(n 2 ) time so we're keeping it short and precise. Bubble sort start with first two element, compare them to check which one is greater. And swap it. BUBBLE SORTING 106

87. Algorithm Bubble sorting 107

88. def bubble_sort ( arr ): n = len ( arr ) for i in range(n): for j in range(n - i - 1): if arr [j] > arr [j + 1]: # Swap if out of order arr [j], arr [j + 1] = arr [j + 1], arr [j] # Example a = [5, 3, 1, 4, 2] bubble_sort (a) print("Sorted:", a)

89. Insertion Sort

90. ALGORITHM OF INSERTION SORT

91. Selection Sort

92. Quick Sort Algorithm Quick sort is based on divide-and-conquer strategy Quick sort is thus in-place, divide-and-conquer based massively recursive sort technique This technique reduces unnecessary swaps and moves the element at great distance in one move

93. Quick Sort Algorithm The recursive algorithm consists of four steps: If there is one or less element in the array to be sorted, return immediately Pick an element in the array to serve as a ‘pivot’ usually the left-most element in the list) Partition the array into two parts—one with elements smaller than the pivot and the other with elements larger than the pivot by traversing from both the ends and performing swaps if needed Recursively repeat the algorithm for both partitions

94. Quick Sort Algorithm

95. Quick Sort Algorithm

96. Quick Sort Algorithm

97. Quick Sort Algorithm

98. Quick Sort Algorithm

99. Quick Sort Algorithm

100. Quick Sort Algorithm

101. Quick Sort Algorithm

102. Quick Sort Algorithm

103. Merge Sort Algorithm Merge sort is a sorting technique based on divide and conquer technique . With Average case and worst-case time complexity being Ο(n log n) , it is one of the most respected algorithms. Merge sort first divides the array into equal halves and then combines them in a sorted manner.

104. The most common algorithm used in external sorting is the merge sort Merging is the process of combining two or more sorted files into the third sorted file We can use a techniqueof merging two sorted lists Divide and conquer is a general algorithm design paradigm that is used for mergesort 89 Data Structures Using C++ by Dr Varsha Patil Oxford University Press © 2012 Merge Sort

105. Time Complexity T(n) = O(n logn) 90 Merge Sort

106. How merge sort works a To understand merge sort, we take unsorted array as depicted below − n We know that merge sort first divides the whole array iteratively into equal halves unless the atomic values are achieved . We see here that an array of 8 items is divided into two arrays of size 4.

107. This does not change the sequence of appearance of items in the original. Now we divide these two arrays into halves. We further divide these arrays and we achieve atomic value which can no more be divided .

108. Now, we combine them in exactly same manner they were broken down . We first compare the element for each list and then combine them into another list in sorted manner. We see that 14 and 33 are in sorted positions . We compare 27 and 10 and in the target list of 2 values we put 10 first, followed by 27 . We change the order 19 and 35 . 42 and 44 are placed sequentially.

109. In next iteration of combining phase, we compare lists of two data values, and merge them into a list of four data values placing all in sorted order. After final merging, the list should look like this −

110. Algorithm of merge sort Merge sort keeps on dividing the list into equal halves until it can no more be divided. By definition, if it is only one element in the list , it is sorted. Then merge sort combines smaller sorted lists keeping the new list sorted too . Step 1 − divide the list recursively into two halves until it can no more be divided. Step 2 − if it is only one element in the list it is already sorted, return. Step 3 − merge the smaller lists into new list in sorted order.

111. THANK YOU !!!!! 165