Vertex arrays and sorting polygons by texture

[k0myer01]

Hypothetical situation 1:
brute-force regular grid terrain where any given triangle could have one of 10 different textures. For argument sake, they are randomly assigned.

Hypothetical situation 2:
100 cubes where any face of any cube has one of 6 textures randomly assigned.

Assume that proceedures have been executed to decide what texture should go where, so that the question is HOW to sort the polygons by texture while still using vertex arrays.


Observation:
It would seem like this wouldn't be a really big deal if
there could be a Triangle class something like this:

Triangle
{
  float x1, y1, z1; // vertex one
  float x2, y2, z2; // vertex two
  float x3, y3, z3; // vertex three

  int textureID; // used for sorting

  float tx1, ty1 // texCoord
  float tx2, ty2 // texCoord
  float tx3, ty3 // texCoord

  // etc...
}

Problems:
1) If the vertex related data resides in each Triangle object as well as in a sorted vertex array, there is double memory use. Also, there would be a tremendous amount of duplicate data as triangle objects would share verticies. This type class doesn't seem viable

2) Once the data was in the sorted vertex arrays, how in the world would you make use of something like a triangle strip when the polygons are no longer in their normal 'physical' order?

3) It would seem that there would have to be one large
'master' vertex array for each type of data that all poly data would be pooled into after sorting the polys themselves based on tex ID. Since objects in the scene might be removed or added from visiblility (death / spawn of a creature etc.) that would necessitate updating the contents of the 'master' vertex array every frame, which sounds very busy.

Well, that's all I can think of for now.  It seems like it would be much easier if there was a textureID vertex array...then you could sort that and use the results to sort the others as well.

Thanks for the help