Brachot 16b (Chapter 2, halachah 4)
Mishnah: One who reads (Kriat Shema) out of order has not fulfilled his obligation.
Gemara: Rebbi Yonah says that Rebbi Nachman bar Adda and Rebbi Yosi says that Rebbi Nachman Sabba taught "V'Hayu" (and they will be, from the text of the Shma) means that (they should be read) like it is (meaning in order). It is taught: thus it is as well with Hallel and the reading of the Megillah. It is easy to understand regarding Megillah (from now to the end is page 17a) as it is written (Esther 9) "like their writing", however for Hallel it is due this verse: "From the east of the sun until the west, praised is the name of Hashem" (Tehillim 113).
Rebbi Abun says also (because) it is written in order:
"When Israel went out of Egypt" (Tehillim 114) - About the past.
"Not for us, Hashem, not for us" (Tehillim 115) - For these generations.
"I love that Hashem should hear my voice" (Tehillim 116) - For the days of Moshiach.
"Order the festival procession with boughs" (Tehillim 118) - For the days of Gog and Magog.
"You are my G-d and I will thank You" (Tehillim 118) - For the future to come (Le'atid Lavo).
Rebbi Acha in the name of Rebbi Yehoshua (says): Even those that set the prayer set it in order. Three first blessings, three closing blessings, praise of Hashem, and the middle (blessings) the needs of the creations.
Bestow upon us knowledge! (Now that) you have bestowed upon us knowledge, desire our repentance! (Now that) you have desired our repentance, forgive us! (Now that) you have forgiven us, redeem us! (Now that) you have redeemed us, heal our sickness! (Now that) you have healed our sickness, bless our years! (Now that) you have blessed our years, gather us in! (Now that) you have gathered us in, judge us with righteousness! (Now that) you have judged us with righteousness, subdue those that rise up against us! (Now that) you have subdued those that rise up against us, in justice make us righteous. (Now that) you have made us righteous in judgement, build Your house and hear our prayers and desire us within it!
Notice how the order of brachot here does not include any mention of Moshiach or the house of Dovid. The Gemara goes on to say later (when quoting the sources that prove that this is the proper order according to the Tanach) that we mention Dovid in the brachah for Yerushalayim. The Yerushalmi, as opposed to the Bavli, has 18 brachot in the daily prayers, not 19 like we say today in line with the Bavli.