Method for merge sort by representation

1. A computer-implemented method of creating a sorted data array for use in a data recovery system, comprising:

allocating, by the data recovery system, a representation array corresponding to the data array to be sorted, wherein the representation array includes a plurality of representation elements, wherein each of the plurality of representation elements corresponds to a position of one of a plurality of data elements of the data array, wherein the plurality of data elements of the data array include one or more of text, binary data, objects, or a mix thereof, and wherein the data array includes index values in an ascending order;

assigning, by a scan module of the data recovery system, an index value to each of the plurality of representation elements of the representation array based on a value of a corresponding data element of the plurality of data elements of the data array without moving the plurality of data elements of the data array;

swapping, by a sort module of the data recovery system, one of the plurality of data elements of the data array based on the assigned index value of the representation element of the representation array corresponding to the data element of the data array, to match the assigned index value of the representation element to the index value of the data element of the data array;

swapping, by the sort module of the data recovery system, the representation element of the representation array to match the representation element to a corresponding swapped data element of the data array; and

iteratively swapping the remaining data elements of the plurality of data elements of the data array and iteratively swapping the remaining representation elements of the plurality of representation elements of the representation array until the stored index values of the representation array are in a predetermined sorted order.

2. The computer-implemented method of claim 1 , wherein the stored index values of the representation array represent the index values of the corresponding data elements of the data array in a sorted order.

3. The computer-implemented method of claim 1 , wherein the data array comprises a first portion having a first subset of sorted data elements and a second portion having a second subset of sorted data elements.

4. The computer-implemented method of claim 3 , wherein assigning index values comprises merging the first and the second portions by assigning index values to the representation elements corresponding to the data elements of the first and the second portions without moving the data elements of the first and the second portions.

5. The computer-implemented method of claim 4 , wherein merging the first and the second subsets of data elements comprises:

when all of the data elements of the first subset of data elements have been represented by corresponding index values, assigning a next available index value to the representation element corresponding to the next data element of the second subset of data elements that is not represented by a corresponding index value; and

when all of the data elements of the second subset of data elements have been represented by corresponding index values, assigning a next available index value to the representation element corresponding to the next data element of the first subset of data elements that is not represented by a corresponding index value.

6. The computer-implemented method of claim 5 , further comprising:

if a next data element of the first subset of data elements that is not represented by a corresponding index value is greater than next data element of the second subset of data elements that is not represented by a corresponding index value, assigning a next available index value to the representation element corresponding to the next data element of the second subset of data elements that is not represented by a corresponding index value; and

otherwise, assigning a next available index value to the representation element corresponding to the next data element of the first subset of data elements that is not represented by a corresponding index value.

7. The computer-implemented method of claim 4 , wherein merging the first and the second subsets of data elements are performed iteratively until all of the data elements of the first and the second subset of data elements have been represented by corresponding index values.

8. A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations to create a sorted data array for use in a data recovery system, the operations comprising:

allocating, by the data recovery system, a representation array corresponding to the data array to be sorted, wherein the representation array includes a plurality of representation elements, wherein each of the plurality of representation elements corresponds to a position of one of a plurality of data elements of the data array, wherein the plurality of data elements of the data array include one or more of text, binary data, objects, or a mix thereof, and wherein the data array includes index values in an ascending order;

assigning, by a scan module of the data recovery system, an index value to each of the plurality of representation elements of the representation array based on a value of a corresponding data element of the plurality of data elements of the data array without moving the plurality of data elements of the data array;

swapping, by a sort module of the data recovery system, one of the plurality of data elements of the data array based on the assigned index value of the representation element of the representation array corresponding to the data element of the data array, to match the assigned index value of the representation element to the index value of the data element of the data array;

swapping, by the sort module of the data recovery system, the representation element of the representation array to match the representation element to a corresponding swapped data element of the data array; and

iteratively swapping the remaining data elements of the plurality of data elements of the data array and iteratively swapping the remaining representation elements of the plurality of representation elements of the representation array until the stored index values of the representation array are in a predetermined sorted order.

9. The non-transitory machine-readable medium of claim 8 , wherein the stored index values of the representation array represent the index values of the corresponding data elements of the data array in a sorted order.

10. The non-transitory machine-readable medium of claim 8 , wherein the data array comprises a first portion having a first subset of sorted data elements and a second portion having a second subset of sorted data elements.

11. The non-transitory machine-readable medium of claim 10 , wherein assigning index values comprises merging the first and the second portions by assigning index values to the representation elements corresponding to the data elements of the first and the second portions without moving the data elements of the first and the second portions.

12. The non-transitory machine-readable medium of claim 11 , wherein merging the first and the second subsets of data elements comprises:

when all of the data elements of the first subset of data elements have been represented by corresponding index values, assigning a next available index value to the representation element corresponding to the next data element of the second subset of data elements that is not represented by a corresponding index value; and

when all of the data elements of the second subset of data elements have been represented by corresponding index values, assigning a next available index value to the representation element corresponding to the next data element of the first subset of data elements that is not represented by a corresponding index value.

13. The non-transitory machine-readable medium of claim 12 , further comprising:

if a next data element of the first subset of data elements that is not represented by a corresponding index value is greater than next data element of the second subset of data elements that is not represented by a corresponding index value, assigning a next available index value to the representation element corresponding to the next data element of the second subset of data elements that is not represented by a corresponding index value; and

otherwise, assigning a next available index value to the representation element corresponding to the next data element of the first subset of data elements that is not represented by a corresponding index value.

14. The non-transitory machine-readable medium of claim 11 , wherein merging the first and the second subsets of data elements are performed iteratively until all of the data elements of the first and the second subset of data elements have been represented by corresponding index values.

15. A data processing system, comprising:

a processor; and

a memory coupled to the processor to store instructions, which when executed by the processor, cause the processor to perform operations to create a sorted data array for use in a data recovery system, the operations including:

allocating, by the data recovery system, a representation array corresponding to the data array to be sorted, wherein the representation array includes a plurality of representation elements, wherein each of the plurality of representation elements corresponds to a position of one of a plurality of data elements of the data array, wherein the plurality of data elements of the data array include one or more of text, binary data, objects, or a mix thereof, and wherein the data array includes index values in an ascending order;

assigning, by a scan module of the data recovery system, an index value to each of the plurality of representation elements of the representation array based on a value of a corresponding data element of the plurality of data elements of the data array without moving the plurality of data elements of the data array;

swapping, by a sort module of the data recovery system, one of the plurality of data elements of the data array based on the assigned index value of the representation element of the representation array corresponding to the data element of the data array, to match the assigned index value of the representation element to the index value of the data element of the data array; and

swapping, by the sort module of the data recovery system, the representation element of the representation array to match the representation element to a corresponding swapped data element of the data array; and

iteratively swapping the remaining data elements of the plurality of data elements of the data array and iteratively swapping the remaining representation elements of the plurality of representation elements of the representation array until the stored index values of the representation array are in a predetermined sorted order.

16. The data processing system of claim 15 , wherein the stored index values of the representation array represent the index values of the corresponding data elements of the data array in a sorted order.

17. The data processing system of claim 15 , wherein the data array comprises a first portion having a first subset of sorted data elements and a second portion having a second subset of sorted data elements.

18. The data processing system of claim 17 , wherein assigning index values comprises merging the first and the second portions by assigning index values to the representation elements corresponding to the data elements of the first and the second portions without moving the data elements of the first and the second portions.

19. The data processing system of claim 18 , wherein merging the first and the second subsets of data elements comprises:

when all of the data elements of the first subset of data elements have been represented by corresponding index values, assigning a next available index value to the representation element corresponding to the next data element of the second subset of data elements that is not represented by a corresponding index value; and

when all of the data elements of the second subset of data elements have been represented by corresponding index values, assigning a next available index value to the representation element corresponding to the next data element of the first subset of data elements that is not represented by a corresponding index value.

20. The data processing system of claim 19 , further comprising:

if a next data element of the first subset of data elements that is not represented by a corresponding index value is greater than next data element of the second subset of data elements that is not represented by a corresponding index value, assigning a next available index value to the representation element corresponding to the next data element of the second subset of data elements that is not represented by a corresponding index value; and

otherwise, assigning a next available index value to the representation element corresponding to the next data element of the first subset of data elements that is not represented by a corresponding index value.

21. The data processing system of claim 18 , wherein merging the first and the second subsets of data elements are performed iteratively until all of the data elements of the first and the second subset of data elements have been represented by corresponding index values.