test/loops/BoxedLongSort.java

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

import java.util.*;
import java.util.concurrent.*;

class BoxedLongSort {
    static final long NPS = (1000L * 1000 * 1000);

    static int THRESHOLD;
    //    static final int THRESHOLD = 64;

    public static void main(String[] args) throws Exception {
        int procs = 0;
        int n = 1 << 22;
        int reps = 30;
        int sreps = 2;
        try {
            if (args.length > 0)
                procs = Integer.parseInt(args[0]);
            if (args.length > 1)
                n = Integer.parseInt(args[1]);
            if (args.length > 2)
                reps = Integer.parseInt(args[1]);
        }
        catch (Exception e) {
            System.out.println("Usage: java BoxedLongSort threads n reps");
            return;
        }
        if (procs == 0)
            procs = Runtime.getRuntime().availableProcessors();

        THRESHOLD = ((n + 7) >>> 3) / procs;
        //        THRESHOLD = ((n + 15) >>> 4) / procs;
        //        THRESHOLD = ((n + 31) >>> 5) / procs;
        if (THRESHOLD < 64)
            THRESHOLD = 64;

        System.out.println("Threshold = " + THRESHOLD);

        Long[] numbers = new Long[n];
        for (int i = 0; i < n; ++i)
            numbers[i] = Long.valueOf(i);
        Long[] a = new Long[n];
        //        ForkJoinPool pool = new ForkJoinPool(procs);
        ForkJoinPool pool = ForkJoinPool.commonPool();
        seqTest(a, numbers, pool, 1);
        System.out.println(pool);
        parTest(a, numbers, pool, reps);
        System.out.println(pool);
        seqTest(a, numbers, pool, 2);
        System.out.println(pool);
        pool.shutdown();
    }

    static void seqTest(Long[] a, Long[] numbers, ForkJoinPool pool, int reps) {
        int n = numbers.length;
        System.out.printf("Sorting %d longs, %d replications\n", n, reps);
        long start = System.nanoTime();
        for (int i = 0; i < reps; ++i) {
            new RandomRepacker(numbers, a, 0, n, n).invoke();
            //            pool.invoke(new TaskChecker());
            long last = System.nanoTime();
            //            quickSort(a, 0, n-1);
            java.util.Arrays.sort(a);
            long now = System.nanoTime();
            double total = (double)(now - start) / NPS;
            double elapsed = (double)(now - last) / NPS;
            System.out.printf("Arrays.sort   time:  %7.3f total %9.3f\n",
                              elapsed, total);
            if (i == 0)
                checkSorted(a);
        }
    }

    static void parTest(Long[] a, Long[] numbers, ForkJoinPool pool, int reps) throws Exception {
        int n = numbers.length;
        Long[] w = new Long[n];
        System.out.printf("Sorting %d longs, %d replications\n", n, reps);
        long start = System.nanoTime();
        for (int i = 0; i < reps; ++i) {
            //            Arrays.fill(w, 0, n, null);
            new RandomRepacker(numbers, a, 0, n, n).invoke();
            //            Thread.sleep(500);
            //            pool.invoke(new TaskChecker());
            long last = System.nanoTime();
            new Sorter(a, w, 0, n).invoke();
            long now = System.nanoTime();
            //            pool.invoke(new TaskChecker());
            double total = (double)(now - start) / NPS;
            double elapsed = (double)(now - last) / NPS;
            System.out.printf("Parallel sort time:  %7.3f total %9.3f\n",
                              elapsed, total);
            if (i == 0)
                checkSorted(a);
        }
    }

    static final class Sorter extends RecursiveAction {
        final Long[] a;
        final Long[] w;
        final int origin;
        final int n;
        Sorter(Long[] a, Long[] w, int origin, int n) {
            this.a = a; this.w = w; this.origin = origin; this.n = n;
        }

        public void compute() {
            int l = origin;
            if (n <= THRESHOLD) {
                //                Arrays.sort(a, l, l+n);
                quickSort(a, l, l+n-1);
            }
            else { // divide in quarters to ensure sorted array in a not w
                int h = n >>> 1;
                int q = n >>> 2;
                int u = h + q;
                SubSorter rs = new SubSorter
                    (new Sorter(a, w, l+h, q),
                     new Sorter(a, w, l+u, n-u),
                     new Merger(a, w, l+h, q, l+u, n-u, l+h, null));
                rs.fork();
                Sorter rl = new Sorter(a, w, l+q, h-q);
                rl.fork();
                (new Sorter(a, w, l,   q)).compute();
                rl.join();
                (new Merger(a, w, l,   q, l+q, h-q, l, null)).compute();
                rs.join();
                new Merger(w, a, l, h, l+h, n-h, l, null).compute();
            }
        }
    }

    static final class SubSorter extends RecursiveAction {
        final Sorter left;
        final Sorter right;
        final Merger merger;
        SubSorter(Sorter left, Sorter right, Merger merger) {
            this.left = left; this.right = right; this.merger = merger;
        }
        public void compute() {
            right.fork();
            left.compute();
            right.join();
            merger.compute();
        }
    }

    static final class Merger extends RecursiveAction {
        final Long[] a; final Long[] w;
        final int lo; final int ln; final int ro; final int rn; final int wo;
        Merger next;
        Merger(Long[] a, Long[] w, int lo, int ln, int ro, int rn, int wo,
               Merger next) {
            this.a = a;    this.w = w;
            this.lo = lo;  this.ln = ln;
            this.ro = ro;  this.rn = rn;
            this.wo = wo;
            this.next = next;
        }

        /**
         * Merge left and right by splitting left in half,
         * and finding index of right closest to split point.
         * Uses left-spine decomposition to generate all
         * merge tasks before bottomming out at base case.
         */
        public final void compute() {
            Merger rights = null;
            Long[] a = this.a;
            Long[] w = this.w;
            int ln = this.ln;
            int rn = this.rn;
            int l = this.lo;
            int r = this.ro;
            int k = this.wo;
            while (ln > THRESHOLD && rn > 4) {
                int lh = ln >>> 1;
                int lm = l + lh;
                Long split = a[lm];
                long ls = split.longValue();
                int rl = 0;
                int rh = rn;
                while (rl < rh) {
                    int rm = (rl + rh) >>> 1;
                    if (ls <= a[r + rm].longValue())
                        rh = rm;
                    else
                        rl = rm + 1;
                }
                (rights = new Merger(a, w, lm, ln-lh, r+rh, rn-rh, k+lh+rh, rights)).fork();
                rn = rh;
                ln = lh;
            }

            int lFence = l + ln;
            int rFence = r + rn;
            for (Long t;;) {
                if (l < lFence) {
                    Long al = a[l], ar;
                    if (r >= rFence ||
                        al.longValue() <= (ar = a[r]).longValue()) {
                        ++l; t = al;
                    }
                    else {
                        ++r; t = ar;
                    }
                }
                else if (r < rFence)
                    t = a[r++];
                else
                    break;
                w[k++] = t;
            }

            //            merge(nleft, nright);
            if (rights != null)
                collectRights(rights);
        }

        final void merge(int nleft, int nright) {
            int l = lo;
            int lFence = lo + nleft;
            int r = ro;
            int rFence = ro + nright;
            int k = wo;
            while (l < lFence && r < rFence) {
                Long al = a[l];
                Long ar = a[r];
                Long t;
                if (al <= ar) { ++l; t = al; } else { ++r; t = ar; }
                w[k++] = t;
            }
            while (l < lFence)
                w[k++] = a[l++];
            while (r < rFence)
                w[k++] = a[r++];
        }

        static void collectRights(Merger rt) {
            while (rt != null) {
                Merger next = rt.next;
                rt.next = null;
                if (rt.tryUnfork()) rt.compute(); else rt.join();
                rt = next;
            }
        }

    }

    static void checkSorted(Long[] a) {
        int n = a.length;
        for (int i = 0; i < n - 1; i++) {
            if (a[i] > a[i+1]) {
                throw new Error("Unsorted at " + i + ": " +
                                a[i] + " / " + a[i+1]);
            }
        }
    }

    static void seqRandomFill(Long[] array, int lo, int hi) {
        ThreadLocalRandom rng = ThreadLocalRandom.current();
        for (int i = lo; i < hi; ++i)
            array[i] = rng.nextLong();
    }

    static final class RandomFiller extends RecursiveAction {
        final Long[] array;
        final int lo, hi;
        RandomFiller(Long[] array, int lo, int hi) {
            this.array = array; this.lo = lo; this.hi = hi;
        }
        public void compute() {
            if (hi - lo <= THRESHOLD) {
                Long[] a = array;
                ThreadLocalRandom rng = ThreadLocalRandom.current();
                for (int i = lo; i < hi; ++i)
                    a[i] = rng.nextLong();
            }
            else {
                int mid = (lo + hi) >>> 1;
                RandomFiller r = new RandomFiller(array, mid, hi);
                r.fork();
                (new RandomFiller(array, lo, mid)).compute();
                r.join();
            }
        }
    }

    static final class RandomRepacker extends RecursiveAction {
        final Long[] src;
        final Long[] dst;
        final int lo, hi, size;
        RandomRepacker(Long[] src, Long[] dst,
                       int lo, int hi, int size) {
            this.src = src; this.dst = dst;
            this.lo = lo; this.hi = hi; this.size = size;
        }

        public final void compute() {
            Long[] s = src;
            Long[] d = dst;
            int l = lo, h = hi, n = size;
            if (h - l > THRESHOLD) {
                int m = (l + h) >>> 1;
                invokeAll(new RandomRepacker(s, d, l, m, n),
                          new RandomRepacker(s, d, m, h, n));
            }
            else {
                ThreadLocalRandom rng = ThreadLocalRandom.current();
                for (int i = l; i < h; ++i)
                    d[i] = s[rng.nextInt(n)];
            }
        }
    }

    static final int INSERTION_SORT_THRESHOLD = 8;

    static void quickSort(Long[] a, int lo, int hi) {
        for (;;) {
            if (hi - lo <= INSERTION_SORT_THRESHOLD) {
                for (int i = lo + 1; i <= hi; i++) {
                    Long t = a[i];
                    long tv = t.longValue();
                    int j = i - 1;
                    while (j >= lo && tv < a[j].longValue()) {
                        a[j+1] = a[j];
                        --j;
                    }
                    a[j+1] = t;
                }
                return;
            }

            int mid = (lo + hi) >>> 1;
            if (a[lo].longValue() > a[mid].longValue()) {
                Long t = a[lo]; a[lo] = a[mid]; a[mid] = t;
            }
            if (a[mid].longValue() > a[hi].longValue()) {
                Long t = a[mid]; a[mid] = a[hi]; a[hi] = t;
                if (a[lo].longValue() > a[mid].longValue()) {
                    Long u = a[lo]; a[lo] = a[mid]; a[mid] = u;
                }
            }

            long pivot = a[mid].longValue();
            int left = lo+1;
            int right = hi-1;
            for (;;) {
                while (pivot < a[right].longValue())
                    --right;
                while (left < right && pivot >= a[left].longValue())
                    ++left;
                if (left < right) {
                    Long t = a[left]; a[left] = a[right]; a[right] = t;
                    --right;
                }
                else break;
            }

            if (left - lo <= hi - right) {
                quickSort(a, lo, left);
                lo = left + 1;
            }
            else {
                quickSort(a, right, hi);
                hi = left;
            }
        }
    }

}
Revision:	1.13
Committed:	Sat Sep 12 18:12:20 2015 UTC (8 years, 7 months ago) by dl
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.12:	+8 -6 lines
Log Message:	Use commonPool
#	User	Rev	Content
1	dl	1.1	/*
2			* Written by Doug Lea with assistance from members of JCP JSR-166
3			* Expert Group and released to the public domain, as explained at
4	jsr166	1.5	* http://creativecommons.org/publicdomain/zero/1.0/
5	dl	1.1	*/
6
7	jsr166	1.10	import java.util.*;
8	dl	1.1	import java.util.concurrent.*;
9
10			class BoxedLongSort {
11			static final long NPS = (1000L * 1000 * 1000);
12
13			static int THRESHOLD;
14	dl	1.7	// static final int THRESHOLD = 64;
15	dl	1.1
16	jsr166	1.6	public static void main(String[] args) throws Exception {
17	dl	1.1	int procs = 0;
18			int n = 1 << 22;
19	dl	1.13	int reps = 30;
20	dl	1.1	int sreps = 2;
21			try {
22			if (args.length > 0)
23			procs = Integer.parseInt(args[0]);
24			if (args.length > 1)
25			n = Integer.parseInt(args[1]);
26			if (args.length > 2)
27			reps = Integer.parseInt(args[1]);
28			}
29			catch (Exception e) {
30			System.out.println("Usage: java BoxedLongSort threads n reps");
31			return;
32			}
33	dl	1.7	if (procs == 0)
34			procs = Runtime.getRuntime().availableProcessors();
35	jsr166	1.2
36	dl	1.7	THRESHOLD = ((n + 7) >>> 3) / procs;
37			// THRESHOLD = ((n + 15) >>> 4) / procs;
38			// THRESHOLD = ((n + 31) >>> 5) / procs;
39			if (THRESHOLD < 64)
40			THRESHOLD = 64;
41
42			System.out.println("Threshold = " + THRESHOLD);
43
44			Long[] numbers = new Long[n];
45			for (int i = 0; i < n; ++i)
46			numbers[i] = Long.valueOf(i);
47	dl	1.1	Long[] a = new Long[n];
48	dl	1.13	// ForkJoinPool pool = new ForkJoinPool(procs);
49			ForkJoinPool pool = ForkJoinPool.commonPool();
50	dl	1.7	seqTest(a, numbers, pool, 1);
51			System.out.println(pool);
52			parTest(a, numbers, pool, reps);
53			System.out.println(pool);
54			seqTest(a, numbers, pool, 2);
55			System.out.println(pool);
56			pool.shutdown();
57			}
58	dl	1.1
59	dl	1.7	static void seqTest(Long[] a, Long[] numbers, ForkJoinPool pool, int reps) {
60			int n = numbers.length;
61	dl	1.1	System.out.printf("Sorting %d longs, %d replications\n", n, reps);
62	dl	1.7	long start = System.nanoTime();
63	dl	1.1	for (int i = 0; i < reps; ++i) {
64	dl	1.13	new RandomRepacker(numbers, a, 0, n, n).invoke();
65	dl	1.7	// pool.invoke(new TaskChecker());
66	dl	1.1	long last = System.nanoTime();
67	dl	1.7	// quickSort(a, 0, n-1);
68			java.util.Arrays.sort(a);
69			long now = System.nanoTime();
70			double total = (double)(now - start) / NPS;
71			double elapsed = (double)(now - last) / NPS;
72	jsr166	1.8	System.out.printf("Arrays.sort time: %7.3f total %9.3f\n",
73	dl	1.7	elapsed, total);
74	dl	1.1	if (i == 0)
75			checkSorted(a);
76			}
77	dl	1.7	}
78	dl	1.1
79	dl	1.13	static void parTest(Long[] a, Long[] numbers, ForkJoinPool pool, int reps) throws Exception {
80	dl	1.7	int n = numbers.length;
81			Long[] w = new Long[n];
82			System.out.printf("Sorting %d longs, %d replications\n", n, reps);
83			long start = System.nanoTime();
84			for (int i = 0; i < reps; ++i) {
85			// Arrays.fill(w, 0, n, null);
86	dl	1.13	new RandomRepacker(numbers, a, 0, n, n).invoke();
87			// Thread.sleep(500);
88	dl	1.7	// pool.invoke(new TaskChecker());
89	dl	1.1	long last = System.nanoTime();
90	dl	1.13	new Sorter(a, w, 0, n).invoke();
91	dl	1.7	long now = System.nanoTime();
92			// pool.invoke(new TaskChecker());
93			double total = (double)(now - start) / NPS;
94			double elapsed = (double)(now - last) / NPS;
95	jsr166	1.8	System.out.printf("Parallel sort time: %7.3f total %9.3f\n",
96	dl	1.7	elapsed, total);
97	dl	1.1	if (i == 0)
98			checkSorted(a);
99			}
100			}
101
102			static final class Sorter extends RecursiveAction {
103	jsr166	1.2	final Long[] a;
104	dl	1.1	final Long[] w;
105	jsr166	1.2	final int origin;
106	dl	1.1	final int n;
107			Sorter(Long[] a, Long[] w, int origin, int n) {
108			this.a = a; this.w = w; this.origin = origin; this.n = n;
109			}
110
111	jsr166	1.3	public void compute() {
112	dl	1.1	int l = origin;
113	dl	1.7	if (n <= THRESHOLD) {
114			// Arrays.sort(a, l, l+n);
115			quickSort(a, l, l+n-1);
116			}
117	dl	1.1	else { // divide in quarters to ensure sorted array in a not w
118			int h = n >>> 1;
119			int q = n >>> 2;
120			int u = h + q;
121			SubSorter rs = new SubSorter
122			(new Sorter(a, w, l+h, q),
123			new Sorter(a, w, l+u, n-u),
124			new Merger(a, w, l+h, q, l+u, n-u, l+h, null));
125			rs.fork();
126			Sorter rl = new Sorter(a, w, l+q, h-q);
127			rl.fork();
128			(new Sorter(a, w, l, q)).compute();
129			rl.join();
130			(new Merger(a, w, l, q, l+q, h-q, l, null)).compute();
131			rs.join();
132			new Merger(w, a, l, h, l+h, n-h, l, null).compute();
133			}
134			}
135			}
136	jsr166	1.2
137	dl	1.1	static final class SubSorter extends RecursiveAction {
138			final Sorter left;
139			final Sorter right;
140			final Merger merger;
141			SubSorter(Sorter left, Sorter right, Merger merger) {
142			this.left = left; this.right = right; this.merger = merger;
143			}
144			public void compute() {
145			right.fork();
146			left.compute();
147			right.join();
148			merger.compute();
149			}
150			}
151
152			static final class Merger extends RecursiveAction {
153			final Long[] a; final Long[] w;
154			final int lo; final int ln; final int ro; final int rn; final int wo;
155			Merger next;
156			Merger(Long[] a, Long[] w, int lo, int ln, int ro, int rn, int wo,
157			Merger next) {
158			this.a = a; this.w = w;
159			this.lo = lo; this.ln = ln;
160			this.ro = ro; this.rn = rn;
161			this.wo = wo;
162			this.next = next;
163			}
164
165			/**
166			* Merge left and right by splitting left in half,
167			* and finding index of right closest to split point.
168			* Uses left-spine decomposition to generate all
169			* merge tasks before bottomming out at base case.
170			*/
171			public final void compute() {
172			Merger rights = null;
173	dl	1.7	Long[] a = this.a;
174			Long[] w = this.w;
175			int ln = this.ln;
176			int rn = this.rn;
177			int l = this.lo;
178			int r = this.ro;
179			int k = this.wo;
180			while (ln > THRESHOLD && rn > 4) {
181			int lh = ln >>> 1;
182			int lm = l + lh;
183			Long split = a[lm];
184			long ls = split.longValue();
185	dl	1.1	int rl = 0;
186	dl	1.7	int rh = rn;
187	dl	1.1	while (rl < rh) {
188	dl	1.7	int rm = (rl + rh) >>> 1;
189			if (ls <= a[r + rm].longValue())
190			rh = rm;
191	dl	1.1	else
192	dl	1.7	rl = rm + 1;
193	dl	1.1	}
194	dl	1.7	(rights = new Merger(a, w, lm, ln-lh, r+rh, rn-rh, k+lh+rh, rights)).fork();
195			rn = rh;
196			ln = lh;
197	dl	1.1	}
198	jsr166	1.2
199	dl	1.7	int lFence = l + ln;
200			int rFence = r + rn;
201			for (Long t;;) {
202			if (l < lFence) {
203			Long al = a[l], ar;
204			if (r >= rFence \|\|
205			al.longValue() <= (ar = a[r]).longValue()) {
206	jsr166	1.8	++l; t = al;
207			}
208			else {
209			++r; t = ar;
210	dl	1.7	}
211			}
212			else if (r < rFence)
213			t = a[r++];
214	jsr166	1.8	else
215	dl	1.7	break;
216			w[k++] = t;
217			}
218
219			// merge(nleft, nright);
220	jsr166	1.2	if (rights != null)
221	dl	1.1	collectRights(rights);
222			}
223
224			final void merge(int nleft, int nright) {
225			int l = lo;
226			int lFence = lo + nleft;
227			int r = ro;
228			int rFence = ro + nright;
229			int k = wo;
230			while (l < lFence && r < rFence) {
231			Long al = a[l];
232			Long ar = a[r];
233			Long t;
234			if (al <= ar) { ++l; t = al; } else { ++r; t = ar; }
235			w[k++] = t;
236			}
237			while (l < lFence)
238			w[k++] = a[l++];
239			while (r < rFence)
240			w[k++] = a[r++];
241			}
242
243			static void collectRights(Merger rt) {
244			while (rt != null) {
245			Merger next = rt.next;
246			rt.next = null;
247			if (rt.tryUnfork()) rt.compute(); else rt.join();
248			rt = next;
249			}
250			}
251
252			}
253
254	jsr166	1.6	static void checkSorted(Long[] a) {
255	dl	1.1	int n = a.length;
256			for (int i = 0; i < n - 1; i++) {
257			if (a[i] > a[i+1]) {
258	jsr166	1.2	throw new Error("Unsorted at " + i + ": " +
259	dl	1.1	a[i] + " / " + a[i+1]);
260			}
261			}
262			}
263
264			static void seqRandomFill(Long[] array, int lo, int hi) {
265			ThreadLocalRandom rng = ThreadLocalRandom.current();
266			for (int i = lo; i < hi; ++i)
267			array[i] = rng.nextLong();
268			}
269
270			static final class RandomFiller extends RecursiveAction {
271			final Long[] array;
272			final int lo, hi;
273			RandomFiller(Long[] array, int lo, int hi) {
274			this.array = array; this.lo = lo; this.hi = hi;
275			}
276			public void compute() {
277			if (hi - lo <= THRESHOLD) {
278			Long[] a = array;
279			ThreadLocalRandom rng = ThreadLocalRandom.current();
280			for (int i = lo; i < hi; ++i)
281			a[i] = rng.nextLong();
282			}
283			else {
284			int mid = (lo + hi) >>> 1;
285			RandomFiller r = new RandomFiller(array, mid, hi);
286			r.fork();
287			(new RandomFiller(array, lo, mid)).compute();
288			r.join();
289			}
290			}
291			}
292
293	dl	1.7	static final class RandomRepacker extends RecursiveAction {
294			final Long[] src;
295			final Long[] dst;
296			final int lo, hi, size;
297	jsr166	1.8	RandomRepacker(Long[] src, Long[] dst,
298	dl	1.7	int lo, int hi, int size) {
299			this.src = src; this.dst = dst;
300			this.lo = lo; this.hi = hi; this.size = size;
301			}
302	jsr166	1.8
303	dl	1.7	public final void compute() {
304			Long[] s = src;
305			Long[] d = dst;
306			int l = lo, h = hi, n = size;
307			if (h - l > THRESHOLD) {
308			int m = (l + h) >>> 1;
309			invokeAll(new RandomRepacker(s, d, l, m, n),
310			new RandomRepacker(s, d, m, h, n));
311			}
312			else {
313			ThreadLocalRandom rng = ThreadLocalRandom.current();
314			for (int i = l; i < h; ++i)
315			d[i] = s[rng.nextInt(n)];
316			}
317			}
318			}
319
320			static final int INSERTION_SORT_THRESHOLD = 8;
321
322			static void quickSort(Long[] a, int lo, int hi) {
323			for (;;) {
324			if (hi - lo <= INSERTION_SORT_THRESHOLD) {
325			for (int i = lo + 1; i <= hi; i++) {
326			Long t = a[i];
327			long tv = t.longValue();
328			int j = i - 1;
329			while (j >= lo && tv < a[j].longValue()) {
330			a[j+1] = a[j];
331			--j;
332			}
333			a[j+1] = t;
334			}
335			return;
336			}
337
338			int mid = (lo + hi) >>> 1;
339			if (a[lo].longValue() > a[mid].longValue()) {
340			Long t = a[lo]; a[lo] = a[mid]; a[mid] = t;
341			}
342			if (a[mid].longValue() > a[hi].longValue()) {
343			Long t = a[mid]; a[mid] = a[hi]; a[hi] = t;
344			if (a[lo].longValue() > a[mid].longValue()) {
345			Long u = a[lo]; a[lo] = a[mid]; a[mid] = u;
346			}
347			}
348
349			long pivot = a[mid].longValue();
350			int left = lo+1;
351			int right = hi-1;
352			for (;;) {
353			while (pivot < a[right].longValue())
354			--right;
355			while (left < right && pivot >= a[left].longValue())
356			++left;
357			if (left < right) {
358			Long t = a[left]; a[left] = a[right]; a[right] = t;
359			--right;
360			}
361			else break;
362			}
363
364			if (left - lo <= hi - right) {
365			quickSort(a, lo, left);
366			lo = left + 1;
367			}
368			else {
369			quickSort(a, right, hi);
370			hi = left;
371			}
372			}
373			}
374
375	dl	1.1	}