How to sort nearly sorted array in the fastest time possible? (Java)

Question

I have an array of values which is almost, but not quite sorted, with a few values displaced (say, 50 in 100000). How to sort it most efficiently? (performance is absolutely crucial here and should be way faster than O(N)).

I know about smoothsort, but I can't find Java implementation. Does anyone know whether it is already implemented? Or what I can use for this task instead of smoothsort?

You can't sort it faster than O(N), since that is the time you need to determine if your array is sorted at all. — Botz3000, Sep 07 '09 at 20:20
There may be additional information about the array. Say the displaced member could all be at the end, then you could sort those (O(m log m)) and then act as if they were inserted (O(m log log n) to O(m log n) to find the insert positions). — Tom Hawtin - tackline, Sep 07 '09 at 21:02
it may require different hardware but network sorting can sort in O((log n)^2).Refer to link [network sorting](http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap28.htm) — Himanshu Pandey, Aug 25 '13 at 05:56

score 19 · Accepted Answer · edited May 31 '12 at 22:55

19

Actually, the Wikipedia contains a Java implementation of smoothsort. You can find it here:

http://en.wikipedia.org/wiki/Smoothsort.

edited May 31 '12 at 22:55

dplante

2,445
3
21
27

answered Sep 07 '09 at 20:23

Andrey Adamovich

20,285
14
94
132

1

It doesn't perform that well on benchmark I've made. It has nice algorithmic properties, but the cache behavior is horrible. – deadalnix May 06 '14 at 18:02
The Java implementation was removed from the article. Original code [available below](http://stackoverflow.com/questions/1390832/how-to-sort-nearly-sorted-array-in-the-fastest-time-possible-java/28352545#28352545). – 11101101b Feb 05 '15 at 19:39

score 10 · Answer 2 · answered Sep 07 '09 at 20:32

10

Cocktail Sort

If you want a simple algorithm that's easy to implement, you could do a cocktail sort. It would work reasonably well on nearly-sorted input.

answered Sep 07 '09 at 20:32

DigitalRoss

143,651
25
248
329

1

@Henk: same here. In high school I implemented it as an improvement over bubble sort, but I never knew there was a name for it. – R. Martinho Fernandes Sep 07 '09 at 20:50

Roee Adler · Answer 3 · 2009-09-07T20:33:46.920

7

As Botz3000 noted, you can't perform such an operation faster than O(N). The most basic element of any algorithm would be to find those entries in the array that are out of order. This requires O(N), even before you figure out what to do with them.

If indeed the number of "out-of-order" elements is orders of magnitude below the total number of elements, you could use the following algorithm (assuming linked list):

Find all out-of-order items and extract the from the original list to a separate list, O(N)
The result is two lists: a sorted list and a short extracted list
For each of the extracted elements, insert them into the sorted list. That would be O(log(N)) for each, total is O(Xlog(N)), where X is the number of the extracted elements. If X is very small relative to N, you end up with a total of O(N).

edited Sep 07 '09 at 20:33

answered Sep 07 '09 at 20:23

Roee Adler

33,434
32
105
133

2

Actually is not that difficult to prove. You can prove it by calculating the limit of xlog(n) when x/n -> 0. – R. Martinho Fernandes Sep 07 '09 at 20:30
1

How to you derive the O(log N) in step 3? When using a linked list, binary search might be hard to do... – Dirk Sep 07 '09 at 20:32
@Dirk: even if you can'd do binary search, you can insert all elements in O(XN) time, which for small Xs, yields O(N). – R. Martinho Fernandes Sep 07 '09 at 20:35
@Martinho: thanks, good point, I removed the "difficult" statement. – Roee Adler Sep 07 '09 at 20:37
Step 1 in your algorithm is a major flaw. You can't easilly *define*, let alone *select* out-of-order elements. Especially for O(N). – P Shved Sep 07 '09 at 20:40
@Martinho: Yes. For X sufficiently small when compared to N the algorithm is essentially O(N). I just stumbled over the "log N". – Dirk Sep 07 '09 at 20:41
@Pavel: I don't understand your comment. If you go over a sorted list, and test for all items whether a[i-1] <= a[i] <= a[i+1], you can easily find all out-of-order elements in O(N) – Roee Adler Sep 07 '09 at 20:42
@Dirk: despite my correction you still raise an interesting point: binary search in a linked list is hard at best, impossible at worse. If I know how many elements are in the list I can take advantage of that and in step 1 get some anchors for binary search later on. – R. Martinho Fernandes Sep 07 '09 at 20:45
@Rax: the invariant is even weaker. a[i-1] <= a[i] for all i > 1 is enough. – R. Martinho Fernandes Sep 07 '09 at 20:46
2

@Rax: yes, you can find them, but it may happen that the *amount of so-called "out-of-order" elements will also happen to be O(N)*. Even if the array had smaller number of them when you look at it. Consider [1,5,10,2,3,4,5,6,7,8,9,10,11]. Brute-force algorithm will call elements 2 to 10 out-of-order. That won't make any sense on the later steps. – P Shved Sep 07 '09 at 20:48
1

As cleared in this question: http://stackoverflow.com/questions/1390960/how-do-i-select-all-elements-in-a-list-that-are-out-of-order, step one would take O(N log N) time, overshadowing the other parts of the algorithm, so it won't run in O(N) time. – R. Martinho Fernandes Sep 07 '09 at 21:30

score 6 · Answer 4 · answered Nov 09 '10 at 07:09

There are many good algorithms for this.

Smoothsort is my personal favorite... I actually worked all the math out here if you're curious why it works so well.

A fairly good algorithm for already-sorted data is natural mergesort, which is a bottom-up version of mergesort that works by treating the input as a sequence of sorted subranges, then making multiple passes over the range merging adjacent sorted ranges. It runs in O(n) time if the data is already sorted (because it can detect that there's only one sorted range), and O(n lg n) in the worst case. This algorithm works quite well if the data is "block sorted"; that is, it consists of a lot of sorted blocks placed right next to one another.

Straight insertion sort definitely works well for mostly-sorted data, but can degenerate very badly on a lot of inputs. Some really good sorts (like introsort) actually use this property of insertion sort to do a "cleanup step" on the input.

+1000000 for your article about smoothsort - as you say, it's fascinating but woefully underdocumented (and EWD's original note on it is a highly frustrating read), so your article is both a nourishing meal *and* a soothing balm. — Tom Anderson, Nov 29 '10 at 12:18

score 4 · Answer 5 · edited Sep 07 '09 at 22:04

4

[Sun] JDK7 has (or will have) an implementation of Tim sort (from Python). It's a merge sort that takes advantage of order already existing in the array.

edited Sep 07 '09 at 22:04

R. Martinho Fernandes

228,013
71
433
510

answered Sep 07 '09 at 20:58

Tom Hawtin - tackline

145,806
30
211
305

Could you please either provide a link or explain yourself how tim sort works? – R. Martinho Fernandes Sep 07 '09 at 21:36
Ok, found it and added the link. – R. Martinho Fernandes Sep 07 '09 at 22:05
Tim sort was first implemented for python, and when some java guy (I think it was josh bloch) saw it, he said "we need to get that into java" http://svn.python.org/projects/python/trunk/Objects/listsort.txt – Peter Recore Sep 07 '09 at 22:07
I said the same thing! Thanks for pointing out this pretty good, but less known algorithm. – R. Martinho Fernandes Sep 07 '09 at 22:13

score 3 · Answer 6 · answered Nov 21 '09 at 18:10

Smoothsort or Timsort are great algorithms, and would be sensible things to use.

I'd add that what you might not realise is that the humble insertion sort is adaptive. Indeed, for really almost sorted lists, as you seem to have, my understanding (which i can't back up with a reference) is that it's faster than the more sophisticated algorithms. The problem is that if the input isn't almost-sorted, it rapidly degrades to O(n^2). Still, it's very simple to implement correctly, so if you know for sure that your input is always almost-sorted, it would be a good choice.

H H · Answer 7 · 2009-09-08T20:08:58.993

2

Just to put it on the table, a well implemented bubble-sort would certainly be the simplest algorithm here. With a worst-case of O(n*m), m being the number of displacements. The m part depends heavily on the pattern of displacements, usually total complexity would be O(n).

edited Sep 08 '09 at 20:08

answered Sep 07 '09 at 20:35

H H

263,252
30
330
514

score 0 · Answer 8 · answered Sep 07 '09 at 20:35

0

You are right about the impossibility of reaching O(N), but assuming a multi-core machine (which I have), we can cheat a little by using a parallel sorting algorithm.

answered Sep 07 '09 at 20:35

Alexander Temerev

2,654
3
27
34

Well, the algorithm still runs in O(N). O(N/2) is O(N). – R. Martinho Fernandes Sep 07 '09 at 20:38
3

@Martinho: unless you have a number of cores that grows with the size of the input :) – Roee Adler Sep 07 '09 at 20:39
@Rax: something that takes advantage of parallel universes, like quantum bogosort http://en.wikipedia.org/wiki/Bogosort#Quantum_Bogosort? – R. Martinho Fernandes Sep 07 '09 at 20:43
@Martinho: hilarious, wasn't aware of it – Roee Adler Sep 07 '09 at 20:44
By the way, if you use a parallel sort (especially those of the divide-and-conquer variety) don't forget to use a cutoff to switch to a sequential sort at some point, when the parallelism overhead outweights its benefits. – R. Martinho Fernandes Sep 07 '09 at 21:08

score 0 · Answer 9 · answered Sep 07 '09 at 20:55

Implement what we called in school a Shell's sort. That's bubblesorting sub-arrays. A sub-array with step k is an array of elements with indicies 0, k, 2k, 3k...

If you choose k = 3i+1, and perform multiple bubble sorts, starting from higher i-s downto 0, the times will be smaller on nearly-sorted array.

score 0 · Answer 10 · answered Feb 05 '15 at 19:36

This is the original Java implementation of Smoothsort that used to be available via the Wikipedia article.

// by keeping these constants, we can avoid the tiresome business
// of keeping track of Dijkstra's b and c. Instead of keeping
// b and c, I will keep an index into this array.

static final int LP[] = { 1, 1, 3, 5, 9, 15, 25, 41, 67, 109,
    177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529, 21891,
    35421, 57313, 92735, 150049, 242785, 392835, 635621, 1028457,
    1664079, 2692537, 4356617, 7049155, 11405773, 18454929, 29860703,
    48315633, 78176337, 126491971, 204668309, 331160281, 535828591,
    866988873 // the next number is > 31 bits.
};

public static <C extends Comparable<? super C>> void sort(C[] m,
    int lo, int hi) {
  int head = lo; // the offset of the first element of the prefix into m

  // These variables need a little explaining. If our string of heaps
  // is of length 38, then the heaps will be of size 25+9+3+1, which are
  // Leonardo numbers 6, 4, 2, 1. 
  // Turning this into a binary number, we get b01010110 = 0x56. We represent
  // this number as a pair of numbers by right-shifting all the zeros and 
  // storing the mantissa and exponent as "p" and "pshift".
  // This is handy, because the exponent is the index into L[] giving the
  // size of the rightmost heap, and because we can instantly find out if
  // the rightmost two heaps are consecutive Leonardo numbers by checking
  // (p&3)==3

  int p = 1; // the bitmap of the current standard concatenation >> pshift
  int pshift = 1;

  while (head < hi) {
    if ((p & 3) == 3) {
      // Add 1 by merging the first two blocks into a larger one.
      // The next Leonardo number is one bigger.
      sift(m, pshift, head);
      p >>>= 2;
      pshift += 2;
    } else {
      // adding a new block of length 1
      if (LP[pshift - 1] >= hi - head) {
        // this block is its final size.
        trinkle(m, p, pshift, head, false);
      } else {
        // this block will get merged. Just make it trusty.
        sift(m, pshift, head);
      }

      if (pshift == 1) {
        // LP[1] is being used, so we add use LP[0]
        p <<= 1;
        pshift--;
      } else {
        // shift out to position 1, add LP[1]
        p <<= (pshift - 1);
        pshift = 1;
      }
    }
    p |= 1;
    head++;
  }

  trinkle(m, p, pshift, head, false);

  while (pshift != 1 || p != 1) {
    if (pshift <= 1) {
      // block of length 1. No fiddling needed
      int trail = Integer.numberOfTrailingZeros(p & ~1);
      p >>>= trail;
      pshift += trail;
    } else {
      p <<= 2;
      p ^= 7;
      pshift -= 2;

      // This block gets broken into three bits. The rightmost
      // bit is a block of length 1. The left hand part is split into
      // two, a block of length LP[pshift+1] and one of LP[pshift].
      // Both these two are appropriately heapified, but the root
      // nodes are not necessarily in order. We therefore semitrinkle
      // both of them

      trinkle(m, p >>> 1, pshift + 1, head - LP[pshift] - 1, true);
      trinkle(m, p, pshift, head - 1, true);
    }

    head--;
  }
}

private static <C extends Comparable<? super C>> void sift(C[] m, int pshift,
    int head) {
  // we do not use Floyd's improvements to the heapsort sift, because we
  // are not doing what heapsort does - always moving nodes from near
  // the bottom of the tree to the root.

  C val = m[head];

  while (pshift > 1) {
    int rt = head - 1;
    int lf = head - 1 - LP[pshift - 2];

    if (val.compareTo(m[lf]) >= 0 && val.compareTo(m[rt]) >= 0)
      break;
    if (m[lf].compareTo(m[rt]) >= 0) {
      m[head] = m[lf];
      head = lf;
      pshift -= 1;
    } else {
      m[head] = m[rt];
      head = rt;
      pshift -= 2;
    }
  }

  m[head] = val;
}

private static <C extends Comparable<? super C>> void trinkle(C[] m, int p,
    int pshift, int head, boolean isTrusty) {

  C val = m[head];

  while (p != 1) {
    int stepson = head - LP[pshift];

    if (m[stepson].compareTo(val) <= 0)
      break; // current node is greater than head. Sift.

    // no need to check this if we know the current node is trusty,
    // because we just checked the head (which is val, in the first
    // iteration)
    if (!isTrusty && pshift > 1) {
      int rt = head - 1;
      int lf = head - 1 - LP[pshift - 2];
      if (m[rt].compareTo(m[stepson]) >= 0
          || m[lf].compareTo(m[stepson]) >= 0)
        break;
    }

    m[head] = m[stepson];

    head = stepson;
    int trail = Integer.numberOfTrailingZeros(p & ~1);
    p >>>= trail;
    pshift += trail;
    isTrusty = false;
  }

  if (!isTrusty) {
    m[head] = val;
    sift(m, pshift, head);
  }
}

How to sort nearly sorted array in the fastest time possible? (Java)

10 Answers10

Cocktail Sort

Linked