A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Ordered Arrays

The ordered array is almost identical to the “classic” array we saw in the previous chapter. The only difference is that ordered arrays require that the values are always kept—you guessed it—in order. That is, every time a value is added, it gets placed in the proper cell so that the values in the array remain sorted.

For example, let’s take the array [3, 17, 80, 202]:

Assume we want to insert the value 75 into the array. If this array were a classic array, we could insert the 75 at the end, as follows:

As we saw in the previous ...