Data merge method performing data merge operations with identifying valid data of source nodes for next data merge operation, memory storage device, and memory control circuit unit

A memory storage device, comprising:

• a connection interface unit, configured to couple to a host system;
• a rewritable non-volatile memory module, comprising a plurality of physical units;
• and
• a memory control circuit unit, coupled to the connection interface unit and the rewritable non-volatile memory module, wherein
• the memory control circuit unit is configured to start a first data merge operation, and select at least one first physical unit for executing the first data merge operation and at least one second physical unit for executing a second data merge operation from the plurality of physical units,
• the memory control circuit unit further reads first mapping information from the rewritable non-volatile memory module, and copies first valid data collected from the at least one first physical unit to at least one third physical units in the plurality of physical units according to the first mapping information during the first data merge operation,
• the memory control circuit unit is further configured to identify second valid data in the at least one second physical unit according to the first mapping information during the first data merge operation, and
• the memory control circuit unit is further configured to end the first merge operation and after the first merge operation is ended, start the second data merge operation, and copy the second valid data collected from the at least one second physical unit to at least one fourth physical unit in the plurality of physical units based on the identifying performed during the first data merge operation.

A memory control circuit unit for controlling a rewritable non-volatile memory module, wherein the rewritable non-volatile memory module comprises a plurality of physical units, the memory control circuit unit comprising:

• a host interface, configured to couple to a host system;
• a memory interface, configured to couple to the rewritable non-volatile memory module;
• and
• a memory management circuit, coupled to the host interface and the memory interface, wherein
• the memory management circuit is configured to start a first data merge operation, and select at least one first physical unit for executing the first data merge operation and at least one second physical unit for executing a second data merge operation from the plurality of physical units,
• the memory management circuit is further configured to read first mapping information from the rewritable non-volatile memory module, and copy first valid data collected from the at least one first physical unit to at least one third physical unit in the plurality of physical units according to the first mapping information during the first data merge operation,
• the memory management circuit is further configured to identify second valid data in the at least one second physical unit according to the first mapping information during the first data merge operation, and
• the memory management circuit is further configured to end the first merge operation and after the first merge operation is ended, start the second data merge operation, and copy the second valid data collected from the at least one second physical unit to at least one fourth physical unit in the plurality of physical units based on the identifying performed during the first data merge operation.