in the above examplea single-pass merge was used but if the ratio of data to be sorted and available ram is particularly largea multi-pass sorting is used we can first merge only the first half of the sorted chunksthen the other halfand finally merge the two sorted chunks the exact number of passes depends on the following factorssize of the data to be sorted when compared with the available ram physical characteristics of the magnetic disk such as transfer rateseek timeetc applications of external sorting external sorting is used to update master file from transaction file for exampleupdating the employees file based on new hirespromotionsappraisalsand dismissals it is also used in database applications for performing operations like projection and join projection means selecting subset of fields and join means joining two files on common field to create new file whose fields are the union of the fields of the two files external sorting is also used to remove duplicate records points to remember searching refers to finding the position of value in collection of values some of the popular searching techniques are linear searchbinary searchinterpolation searchand jump search linear search works by comparing the value to be searched with every element of the array one by one is sequence until match is found binary search works efficiently with sorted list in this algorithmthe value to be searched is compared with the middle element of the array segment in each step of interpolation searchthe search space for the value to be found is calculated the calculation is done based on the values at the bounds of the search space and the value to be searched jump search is used with sorted lists we first check an element and if it is less than the desired valuethen block of elements is skipped by jumping aheadand the element following this block is checked if the checked element is greater than the desired valuethen we have boundary and we are sure that the desired value lies between the previously checked element and the currently checked element internal sorting deals with sorting the data stored in the memorywhereas external sorting deals with sorting the data stored in files in bubble sortingconsecutive adjacent pairs of elements in the array are compared with each other insertion sort works by moving the current data element past the already sorted values and repeatedly interchanging it with the preceding value until it is in the correct place selection sort works by finding the smallest value and placing it in the first position it then finds the second smallest value and places it in the second position this procedure is repeated until the whole array is sorted merge sort is sorting algorithm that uses the divideconquerand combine algorithmic paradigm divide means partitioning the -element array to be sorted into two sub-arrays of / elements in each subarray conquer means sorting the two sub-arrays recursively using merge sort combine means merging the two sorted sub-arrays of size / each to produce sorted array of elements the running time of merge sort in average case and worst case can be given as ( log nquick sort works by using divide-and-conquer strategy it selects pivot element and rearranges the elements in such way that all elements less than pivot appear before it and all elements greater than pivot appear after it radix sort is linear sorting algorithm that uses the concept of sorting names in alphabetical order heap sort sorts an array in two phases in the first phaseit builds heap of the given array in the second phasethe root element is deleted repeatedly and inserted into an array shell sort is considered as an improvement over insertion sortas it compares elements separated by gap of several positions tree sort is sorting algorithm that sorts numbers by making use of the properties of binary search tree the algorithm first builds binary search tree using the numbers to be sorted and then does an in-order traversal so that the numbers are retrieved in sorted order