Method for sorting data

Patent metadata

Field	Value
Publication number	US-10089379-B2
Application number	US-19308408-A
Country	US
Kind code	B2
Filing date	Aug 18, 2008
Priority date	Aug 18, 2008
Publication date	Oct 2, 2018
Grant date	Oct 2, 2018

Abstract

A sequence of one or more input objects are sorted by identifying a property that is exhibited by a sequence of one or more input objects, determining whether each input object from the sequence of one or more input objects exhibits the property, storing each of the one or more input objects into a buffer, wherein an input object is stored in a first buffer if it exhibits the property and an input object is stored in a second buffer if it does not exhibit the property, sorting each of the one or more input objects in each buffer, and merging the one or more input objects in each buffer into a sequence of one or more input objects.

First claim

What is claimed is:

1. A method for sorting a sequence of one or more input objects, comprising the steps of:
identifying a property that is exhibited by a sequence of one or more input objects, wherein said property indicates whether said sequence of one or more input objects is mostly sorted and is used to select one of a plurality of buffers for storing each input object;
determining whether each input object from the sequence of one or more input objects exhibits the property;
storing each of the one or more input objects into one of said plurality of buffers, wherein an input object is stored in a first buffer when said input object exhibits the property and an input object is stored in a second buffer that takes the input objects that could not be put into the first buffer when said input object does not exhibit the property;
sorting each of the one or more input objects in each buffer, wherein the first buffer is sorted with a first sorting algorithm which is an insertion sort on a local region of the first buffer and the second buffer is sorted with a second sorting algorithm, wherein the second sorting algorithm is a sort algorithm for sorting objects which are not substantially ordered and wherein the first sorting algorithm is different than the second sorting algorithm; and
merging the one or more input objects in each buffer into a sequence of one or more input objects, wherein the first sorting algorithm and the second sorting algorithm are distinct from each other and from a process that performs the merging.

2. The method of claim 1 , wherein the second sorting algorithm is a sort algorithm with general and worst case computation complexity.

3. The method of claim 1 , wherein a region in the first buffer comprises one or more input objects derived from a final end of the sequence of one or more input objects.

4. The method of claim 3 , further comprising determining whether an input object can be at least one of inserted into the region and appended after the region.

5. The method of claim 1 , wherein each buffer is dynamically sized.

6. The method of claim 1 , wherein the property comprises whether the sequence of one or more input objects is at least one of mostly ordered and well clustered.

7. The method of claim 1 , further comprising combining the first buffer and the second buffer into one buffer.

8. The method of claim 7 , further comprising preserving an ordered subset starting from a first end of the one buffer and using a second end of the one buffer to store one or more out of order input objects.

9. The method of claim 7 , wherein a division of the first buffer and the second buffer is dynamic depending on which side an input record falls to.

10. The method of claim 1 , further comprising concurrently sorting the first buffer and the second buffer.

11. The method of claim 1 , further comprising using three or more buffers, wherein all of the three or more buffers except one are used to hold one or more sorted subsets of input objects.

12. The method of claim 11 , wherein each of the three or more buffers comprises a corresponding property.

13. A computer program product comprising a non-transitory computer readable medium having computer readable program code for sorting a sequence of one or more input objects, said computer program product including:
computer readable program code for identifying a property that is exhibited by a sequence of one or more input objects, wherein said property indicates whether said sequence of one or more input objects is mostly sorted and is used to select one of a plurality of buffers for storing each input object;
computer readable program code for determining whether each input object from the sequence of one or more input objects exhibits the property;
computer readable program code for storing each of the one or more input objects into one of said plurality of buffers, wherein an input object is stored in a first buffer if said input object exhibits the property and an input object is stored in a second buffer that takes the input objects that could not be put in the first buffer if said input object does not exhibit the property;
computer readable program code for sorting each of the one or more input objects in each buffer, wherein the first buffer is sorted with a first sorting algorithm which is an insertion sort on a local region of the first buffer and the second buffer is sorted with a second sorting algorithm for sorting objects which are not substantially ordered and wherein the first sorting algorithm is different than the second sorting algorithm; and
computer readable program code for merging the one or more input objects in each buffer into a sequence of one or more input objects, wherein the first sorting algorithm and the second sorting algorithm are distinct from each other and from a process that performs the merging.

14. The computer program product of claim 13 , further comprising computer readable program code for combining the first buffer and the second buffer into one buffer, wherein combining the first buffer and the second buffer into one buffer preserves an ordered subset starting from a first end of the one buffer and using a second end of the one buffer to store one or more out of order input objects.

15. The computer program product of claim 13 , further comprising computer readable program code for concurrently sorting the first buffer and the second buffer.

16. The computer program product of claim 13 , further comprising computer readable program code for using three or more buffers, wherein all of the three or more buffers except one are used to hold one or more sorted subsets of input objects, and wherein each of the three or more buffers comprises a corresponding property.

17. An apparatus for sorting a sequence of one or more input objects, comprising:
a memory; and
at least one processor coupled to said memory and configured to:
identify a property that is exhibited by a sequence of one or more input objects, wherein said property indicates whether said sequence of one or more input objects is mostly sorted and is used to select one of a plurality of buffers for storing each input object;
determine whether each input object from the sequence of one or more input objects exhibits the property;
store each of the one or more input objects into one of said plurality of buffers, wherein an input object is stored in a first buffer if said input object exhibits the property and an input object is stored in a second buffer that takes the input objects that could not be put into the first buffer if said input object does not exhibit the property;
sort each of the one or more input objects in each buffer, wherein the first buffer is sorted with a first sorting algorithm which is an insertion sort on a local region of the first buffer and the second buffer is sorted with a second sorting algorithm for sorting objects which are not substantially ordered and wherein the first sorting algorithm is different than the second sorting algorithm; and
merge the one or more input objects in each buffer into a sequence of one or more input objects, wherein the first sorting algorithm and the second sorting algorithm are distinct from each other and from a process that performs the merge.

18. The apparatus of claim 17 , wherein the at least one processor coupled to said memory is further operative to combine the first buffer and the second buffer into one buffer, wherein combining the first buffer and the second buffer into one buffer preserves an ordered subset starting

Assignees

• Min Hong
• Shuf Yefim
• Franke Hubertus
• Lebovitz Allan Benjamin
• Crone Christopher John
• Hoshikawa Akiko
• IBM

Inventors

• Min Hong
• Shuf Yefim
• Franke Hubertus
• Lebovitz Allan Benjamin
• Crone Christopher John
• Hoshikawa Akiko

Classifications

• G06F16/285 Primary

  Clustering or classification · CPC title

• G06F16/289

  Object oriented databases · CPC title

• G06F7/36

  Combined merging and sorting · CPC title

• G06F17/30607

  Physics · mapped topic

• G06F17/30598 Primary

  Physics · mapped topic