diff --git a/hyracks/hyracks-dataflow-std/src/main/java/edu/uci/ics/hyracks/dataflow/std/sort/FrameSorter.java b/hyracks/hyracks-dataflow-std/src/main/java/edu/uci/ics/hyracks/dataflow/std/sort/FrameSorter.java
index db70a62..76f411b 100644
--- a/hyracks/hyracks-dataflow-std/src/main/java/edu/uci/ics/hyracks/dataflow/std/sort/FrameSorter.java
+++ b/hyracks/hyracks-dataflow-std/src/main/java/edu/uci/ics/hyracks/dataflow/std/sort/FrameSorter.java
@@ -17,6 +17,7 @@
 import java.nio.ByteBuffer;
 import java.util.ArrayList;
 import java.util.List;
+import java.util.Random;
 
 import edu.uci.ics.hyracks.api.comm.IFrameWriter;
 import edu.uci.ics.hyracks.api.context.IHyracksTaskContext;
@@ -48,6 +49,8 @@
     private int[] tPointers;
     private int tupleCount;
 
+    private Random rand = new Random();
+
     public FrameSorter(IHyracksTaskContext ctx, int[] sortFields,
             INormalizedKeyComputerFactory firstKeyNormalizerFactory, IBinaryComparatorFactory[] comparatorFactories,
             RecordDescriptor recordDescriptor) throws HyracksDataException {
@@ -116,6 +119,7 @@
             }
         }
         if (tupleCount > 0) {
+            shuffle(tPointers, 4, tupleCount);
             sort(tPointers, 0, tupleCount);
         }
     }
@@ -240,6 +244,18 @@
         return 0;
     }
 
+    private void shuffle(int[] tPointers, int interval, int tupleCount) {
+        for (int i = tupleCount; i > 1; i--) {
+            int next = rand.nextInt(i) * interval;
+            int target = (i - 1) * interval;
+            for (int j = 0; j < interval; j++) {
+                int drawn = tPointers[next + j];
+                tPointers[next + j] = tPointers[target + j];
+                tPointers[target + j] = drawn;
+            }
+        }
+    }
+
     public void close() {
         this.buffers.clear();
     }