Te comento que yo curse estructura de datos en la facu y me toco ver todo el tema de ordenación y búsqueda. Hay algoritmos super probados y que poseen índices de eficiencia conocidos, por lo que puedes comparar el rendimiento de acuerdo a tu caso en particular. Cada uno de ellos tiene ventajas y desventajas y la elección radica en si las estructuras a buscar son grandes, en si manejas gran cantidad de datos, en si los arreglos estan completamente desordenados o ligeramente desordenados, entre otros.
Te nombro los mas comunes para cada caso.
Búsqueda:
Búsqueda Lineal o secuencial
Búsqueda Binaria
Búsqueda con Hashing
Ordenamiento
BubbleSort
SelectionSort
InsertionSort
ShellSort
FusionSort
QuickSort
Cuenta de Distribucion
Seguramente haya librerias en la web sobre implementaciones. En particular yo tengo implementado los cinco primeros algoritmos de ordenación que te nombre en C++ con templates. Quiza te sirvan de guia para entender el algoritmo, así que si los quieres pídelos