Considering the size of the file, nothing will be fast, however, unless you need to do lots of searches, there is no need to sort the file. You are only interested in the lines that match you search term.

If you don't have many searches to do, then the approach I would take would be to filter the file using unix tools to get the lines of interest. eg:

This will give you the lines containing the data you want in linear time. From there you easily turn it into a perl array.

If you need to do lots of searches, then you will need to consturct an index of some sort, or ingest the whole thing into a database, and let the database engine worry about the index.