Here is something I did to allow me to sort the rows in a sheet. It is not quite developed enough to contribute, but it works for what I needed. Maybe you can find some ideas.

import java.util.Iterator;

import org.apache.poi.ss.usermodel.Cell;
import org.apache.poi.ss.usermodel.Row;
import org.apache.poi.ss.usermodel.Sheet;

public class SheetUtils {
	
	public static final int SORT_ASCENDING = 0;
	public static final int SORT_DESCENDING = 1;
	
	public static void sortSheet(Sheet sh, int start, int end, int col, int order) {
		
		for (int ix = start; ix <= end-1; ix++) {
			for (int iy = ix+1; iy <= end; iy++) {
				Row r1 = sh.getRow(ix);
				Row r2 = sh.getRow(iy);
				boolean swap = false;
				switch (order) {
				case SORT_ASCENDING:
					if (compareCell(r1, r2, col) > 0) {
						swap = true;
					}
					break;
				case SORT_DESCENDING:
					if (compareCell(r1, r2, col) < 0) {
						swap = true;
					}
					break;
				}
				if (swap == true) {
					try {
						swapRows(r1, r2);
					} catch (Exception e) {
						e.printStackTrace();
					}
				}
			}
		}
	}
	
	private static int compareCell(Row r1, Row r2, int col) {
		
		Cell c1 = r1.getCell(col);
		Cell c2 = r2.getCell(col);
		int cmp = compareType(c1, c2);
		
		switch (cmp) {
		case 0:
			switch (c1.getCellType()) {
			case Cell.CELL_TYPE_BOOLEAN:
				if (c1.getBooleanCellValue() == c2.getBooleanCellValue()) {
					return 0;					
				}
				else if (c1.getBooleanCellValue() == true) {
					return 1;
				}
				return -1;
			case Cell.CELL_TYPE_NUMERIC:
				if (c1.getNumericCellValue() < c2.getNumericCellValue()) {
					return -1;
				}
				if (c1.getNumericCellValue() == c2.getNumericCellValue()) {
					return 0;
				}
				return 1;
			case Cell.CELL_TYPE_STRING:
				return c1.getStringCellValue().compareToIgnoreCase(c2.getStringCellValue());
			default:
				return 0;
			}
		default:
			return cmp;
		}
	}

	private static int compareType(Cell c1, Cell c2) {
		
		if (c1.getCellType() == c2.getCellType()) {
			return 0;
		}
		if (c1.getCellType() > c2.getCellType()) {
			return 1;
		}
		return -1;
	}

	public static void swapRows(Row r1, Row r2) throws Exception {
		
		Sheet sh1 = r1.getSheet();
		Sheet sh2 = r2.getSheet();
		if (sh1 != sh2) {
			Throwable e = null;
			throw new Exception("Rows from different sheets", e);
		}
		
		int n1 = r1.getRowNum();
		int n2 = r2.getRowNum();
		
  		try {
			copyRow(sh1, n1, n2);
	  		sh1.removeRow(sh1.getRow(n1));
			copyRow(sh1, n2+1, n1);
			sh1.removeRow(sh1.getRow(n2+1));
			if (n2+2 <= sh1.getLastRowNum()) {
				sh1.shiftRows(n2+2, sh1.getLastRowNum(), -1);
			}
  		} catch (Exception e) {
			e.printStackTrace();
		}
		
	}
	
	public static void copyRow(Sheet sh, int src, int tgt) throws Exception {
		
		Row rs = sh.getRow(src);
		Row rt = sh.getRow(tgt);
		
		if (rs == null) {
			Throwable e = null;
			throw new Exception("Source row missing", e);
		}
		
		if (rt != null) {
			sh.shiftRows(tgt, sh.getLastRowNum(), 1);
		}
		rt = sh.createRow(tgt);
		
		Iterator<Cell> cells = rs.cellIterator();
		while (cells.hasNext()) {
			Cell cs = cells.next();
			int ix = cs.getColumnIndex();
			Cell ct = rt.createCell(ix);
			
			// style
			ct.setCellStyle(cs.getCellStyle());
			
			// type
			ct.setCellType(cs.getCellType());
			
			// data
			switch (cs.getCellType()) {
			case Cell.CELL_TYPE_BLANK:
				ct.setCellValue(cs.getStringCellValue());
				break;
			case Cell.CELL_TYPE_BOOLEAN:
				ct.setCellValue(cs.getBooleanCellValue());
				break;
			case Cell.CELL_TYPE_ERROR:
				ct.setCellErrorValue(cs.getErrorCellValue());
				break;
			case Cell.CELL_TYPE_FORMULA:
				ct.setCellFormula(cs.getCellFormula());
				break;
			case Cell.CELL_TYPE_NUMERIC:
				ct.setCellValue(cs.getNumericCellValue());
				break;
			case Cell.CELL_TYPE_STRING:
				ct.setCellValue(cs.getRichStringCellValue());
			}
			
			// hyperlink
			if (cs.getHyperlink() != null) {
				ct.setHyperlink(cs.getHyperlink());
			}
			
			// comment
			if (cs.getCellComment() != null) {
				ct.setCellComment(cs.getCellComment());
			}
		}
	}

}

Thanks Mark. Though it may not help me completely, but it will help me out to some extent in fixing this issue.