Patent ID: 8706953

Claim:
A method of storing data in a storage medium of a data storage device, comprising: storing input data in the storage medium; and reading the input data from the storage medium and compressing the read input data during a background operation of the data storage device; wherein the background operation comprises a merge operation, and compressing data stored in the storage medium comprises: determining whether a free block can be generated by merging “M” selected memory blocks to be merged using a first merge scheme; performing the merge operation according to the first merge scheme if a free block can be generated by merging the “M” selected memory blocks using the first merge scheme; and performing the merge operation according to a second merge scheme different from the first merge scheme if a free block cannot be generated by merging the “M” selected memory blocks using the first merge scheme; wherein the first merge scheme comprises reading valid data from “M” used memory blocks in the storage medium as the read input data, compressing the read valid data to generate compressed data, and storing the compressed data in free memory blocks of the storage medium; and wherein the second merge scheme comprises reading valid data from “N” used memory blocks in the storage medium as the read input data, where N is greater than M, and storing the read valid data in free memory blocks of the storage medium.