private static ArrayList<String> cities = new ArrayList<String>();;

public static void main(String[] args) throws FileNotFoundException
{
    long elapsed, start, end;
    File file = new File("cities.txt");
    Scanner reader = new Scanner(file);
    HashMap<String, String> data = new HashMap<String, String>();

    while (reader.hasNext())
    {
        String line = reader.nextLine();
        int space = line.lastIndexOf(' ', line.lastIndexOf(' ') - 1);
        String city = line.substring(0, space);
        String state_pop = line.substring(space + 1);
        //for (int i = 0; i < 1000; i++)
        //{
            data.put(city, state_pop);
            cities.add(city);
        //}
    }
    // Unsorted
//      System.out.print("Unsorted: ");
//      for (int i = 0; i < cities.size(); i++)
//          System.out.print(cities.get(i) + "|");
    start = System.currentTimeMillis();
    sort();
    end = System.currentTimeMillis();
    elapsed = end - start;

//      System.out.print("nQuickSort: ");
//      for (int k = 0; k < cities.size(); k++)
//          System.out.print(cities.get(k) + "|");
    System.out.println("nQuikcSort time Elapsed: " + elapsed);
}

public static void sort()
{
    int left = 0;
    int right = cities.size() - 1;
    quickSort (left, right);
}

private static void quickSort(int left, int right)
{
    if (left >= right)
        return;
    String pivot = getMedian(left, right);
    int partition = partition(left, right, pivot);
    quickSort(0, partition - 1);
    quickSort(partition + 1, right);
}

private static int partition(int left, int right, String pivot)
{
    int leftCursor = left - 1;
    int rightCursor = right;
    while (leftCursor < rightCursor)
    {
        while (((Comparable<String>) cities.get(++leftCursor)).compareTo(pivot) < 0);
        while (rightCursor > 0
                && ((Comparable<String>) cities.get(--rightCursor)).compareTo(pivot) > 0);
        if (leftCursor >= rightCursor)
            break;
        else
            swap(leftCursor, rightCursor);
    }
    swap(leftCursor, right);
    return leftCursor;
}

public static String getMedian(int left, int right)
{
    int center = (left + right) / 2;
    if (((Comparable<String>) cities.get(left)).compareTo(cities.get(center)) > 0)
        swap(left, center);
    if (((Comparable<String>) cities.get(left)).compareTo(cities.get(right)) > 0)
        swap(left, right);
    if (((Comparable<String>) cities.get(center)).compareTo(cities.get(right)) > 0)
        swap(center, right);
    swap(center, right);
    return cities.get(right);
}

public static void swap(int left, int right)
{
    String temp = cities.get(left);
    cities.set(left, cities.get(right));
    cities.set(right, temp);
}