For small $n$ your construction is not optimal (e.g. for $n=6$ there is a group of size 120, isomorphic to $S_5$; [$M_{12}$][2]) is an example for $n=12$, the biggest exceptional $n$, it seems). 

But for sufficiently large $n$, your construction is <i>almost</i> optimal; you can still add an extra 2 to the order of your group. Namely, add the permutation $(1,n/2+1)(2,n/2+2)\dots (n/2,n)$. A way to prove that this becomes optimal (for sufficiently large $n$) might go as follows:

* prove that this is the best possible with intransitive groups
* same for imprimitive groups
* for primitive groups, invoke [O'Nan-Scott theorem][1] (eventually, the classification of finite simple groups).

Perhaps there is a better way to deal with the last step, I don't know.


  [1]: http://www.maths.qmul.ac.uk/~raw/talks_files/ONStalk.pdf
  [2]: http://en.wikipedia.org/wiki/Mathieu_group