## Notes on INSERTION while maintaining sorted order

First, let’s handle the case for a simple array of INTEGERS:

```// Insertion into an INTEGER ARRAY while maintaining SORTED ORDER, // and NOT worrying about needing to expand the array size:   // Here's the setup: int integerArray[] = new int[10]; int nData = 4; // we're consuming 4 ints out of 10. integerArray[0] = 3; integerArray[1] = 5; integerArray[2] = 7; integerArray[3] = 9; // int numberToInsert = 6; // the number to insert.   // First, compute the array index at which to insert the number. // Assume the data in integerArray[] is already sorted!! int index = 0; while ((index < nData) && (numberToInsert > integerArray[index])) { index++; }   // Now, shift the data above that index, further downstream. for (int i=nData; i>index; i--){ integerArray[i] = integerArray[i-1]; }   // Finally, insert the new number in the right place. // And don't forget to increment nData. integerArray[index] = numberToInsert; nData++; // // NOTE: you *may* have to handle the case // where nData suddenly exceeds the size of the array...```

Now, here is the same problem, but dealing with inserting an Object into a sorted OBJECT ARRAY.
Note: the use of “setup()” is Processing-specific…

```  // Insertion into an OBJECT ARRAY while maintaining SORTED ORDER, // and NOT worrying about needing to expand the array size:   // Here's the class we'll use for this example: class Thing { int property; Thing (){ property = 0; // initialized to zero } void setProperty(int p){ property = p; } int getProperty(){ return property; } }   //------------------------------------------- void setup(){   // Here's the setup: Thing thingArray[] = new Thing[10]; int nData = 4; // we're consuming 4 Things out of 10. for (int i=0; i<nData; i++){ thingArray[i] = new Thing(); } // Note the use of the accessor method! thingArray[0].setProperty(3); thingArray[1].setProperty(5); thingArray[2].setProperty(7); thingArray[3].setProperty(9);   // The Thing to insert: Thing thingToInsert = new Thing(); thingToInsert.setProperty(6);     //-------------------------------- // HERE'S THE INSERTION:   // First, compute the array index at which to insert the number. // Assume the data in integerArray[] is already sorted. int index = 0; int propertyOfThingToInsert = thingToInsert.getProperty(); while ((index < nData) && (propertyOfThingToInsert > thingArray[index].getProperty())){ index++; }   // Now, shift the data above that index further downstream. for (int i=nData; i>index; i--){ thingArray[i] = thingArray[i-1]; }   // Finally, insert the new number in the right place. // And don't forget to increment nData. thingArray[index] = thingToInsert; nData++; }```