A data writing method for a rewritable non-volatile memory module having a plurality of physical erasing units and a memory control circuit unit and a memory storage apparatus using the same are provided. Each of the physical erasing units has a plurality of physical programming unit sets, and each of the physical programming unit sets has a plurality of physical programming unit. The method includes receiving data and arranging the data to generate a first data stream and a second data stream. The method also includes encoding the first data stream and the second data stream to generate a third data stream, and issuing a programming command sequence to write the first data stream, the second data stream and the third data stream respectively into a first physical programming unit, a second physical programming unit and a third physical programming unit of a physical programming unit set.