Generic list heapsort in Java This is an implementation of heapsort as seen on Programming Pearls, adapted for java List collections. It is working on a copy of the list passed-in on purpose at the moment.

import java.util.ArrayList;
import java.util.List;

public final class HeapSort {

    private HeapSort() {}

    public static &lt;T extends Comparable&lt;T&gt;&gt; List&lt;T&gt; heapSort(List&lt;T&gt; unsortedList) {
        assert unsortedList != null;
        assert unsortedList.size() &gt; 1;
        List&lt;T&gt; sortedList = new ArrayList&lt;T&gt;(unsortedList);
        for (int i = 1; i &lt; sortedList.size(); i++) {
            sortedList = siftUp(sortedList, i);
        }
        for (int i = sortedList.size() - 1; i &gt;= 1; i--) {
            sortedList = swap(sortedList, 0, i);
            sortedList = siftDown(sortedList, i - 1);
        }
        return sortedList;
    }

    private static &lt;T extends Comparable&lt;T&gt;&gt; List&lt;T&gt; siftUp(List&lt;T&gt; unsortedList, int n) {
        assert n &gt; 0;
        for (int i = n;;) {
            if (i == 0) {
                break;
            }
            int p = i / 2;
            if (unsortedList.get(p).compareTo(unsortedList.get(i)) &gt;= 0) {
                break;
            }
            unsortedList = swap(unsortedList, i, p);
            i = p;
        }
        return unsortedList;
    }

    private static &lt;T extends Comparable&lt;T&gt;&gt; List&lt;T&gt; siftDown(List&lt;T&gt; unsortedList, int n) {
        for (int i = 0;;) {
            int c = 2 * (i + 1) - 1;

            if (c &gt; n) {
                break;
            }
            if (c + 1 &lt;= n) {
                if (unsortedList.get(c + 1).compareTo(unsortedList.get(c)) &gt; 0) {
                    c += 1;
                }
            }
            if (unsortedList.get(i).compareTo(unsortedList.get(c)) &gt;= 0) {
                break;
            }
            unsortedList = swap(unsortedList, i, c);
            i = c;
        }
        return unsortedList;
    }

    private static &lt;T&gt; List&lt;T&gt; swap(List&lt;T&gt; list, int firstIndex, int secondIndex) {
        assert list != null;
        assert list.size() &gt; 0;
        assert 0 &lt;= firstIndex;
        assert firstIndex &lt; list.size();
        assert 0 &lt;= secondIndex;
        assert secondIndex &lt; list.size();
        if (firstIndex == secondIndex) {
            return list;
        }
        T tmpT = list.get(secondIndex);
        list.set(secondIndex, list.get(firstIndex));
        list.set(firstIndex, tmpT);
        return list;
    }
}


Should I assert on list size in softDown and siftUp? Is the passing back and forth of list references ok?
for (int i = n;;) {
    if (i == 0) {
        break;
    }


This look very odd instead you can do 

for(int i = n; i &gt; 0;){


Asserts are kinda useless in java, they only work when the jvm is started with the -ea flag (or you do some reflection). instead just test and throw the IllegalArgumentException in the public method and remove the obvious assertions that would throw anyway.