Damn, that's a very open ended question. Did they want many solutions depending on the array? I think I would implement quickSort O(n log n) and talk about other options - Radix Sort for large arrays etc...