the internal array in this classthe insertion algorithm creates new array of larger sizecopies the old array contents to the new arrayand then inserts the new item all this would be invisible to the class user summary arrays in java are objectscreated with the new operator unordered arrays offer fast insertion but slow searching and deletion wrapping an array in class protects the array from being inadvertently altered class interface comprises the methods (and occasionally fieldsthat the class user can access class interface can be designed to make things simple for the class user binary search can be applied to an ordered array the logarithm to the base of number is (roughlythe number of times you can divide by before the result is less than linear searches require time proportional to the number of items in an array binary searches require time proportional to the logarithm of the number of items big notation provides convenient way to compare the speed of algorithms an algorithm that runs in ( time is the besto(log nis goodo(nis fairand ( is pretty bad simple sorting overview as soon as you create significant databaseyou'll probably think of reasons to sort it in various ways you need to arrange names in alphabetical orderstudents by gradecustomers by zip codehome sales by pricecities in order of increasing populationcountries by gnpstars by magnitudeand so on sorting data may also be preliminary step to searching it as we saw in the last binary searchwhich can be applied only to sorted datais much faster than linear search because sorting is so important and potentially so time-consumingit has been the subject of extensive research in computer scienceand some very sophisticated methods have been developed in this we'll look at three of the simpler algorithmsthe bubble sortthe selection sortand the insertion sort each is demonstrated with its own workshop applet in "advanced sorting,we'll look at more sophisticated approachesshellsort and quicksort the techniques described in this while unsophisticated and comparatively sloware nevertheless worth examining besides being easier to understandthey are actually better in some circumstances than the more sophisticated algorithms the insertion sort