fdo#72741, fdo#76607: Backport of Calc sort rework.

This change requires mdds 0.10.3 as the baseline.

Conflicts:
	configure.ac
	sc/inc/fstalgorithm.hxx
	sc/source/core/data/column.cxx
	sc/source/core/data/table3.cxx
	sc/source/ui/docshell/dbdocfun.cxx

Change-Id: Ia6d2bf1ee17e96c30b6d5310f5c49e5a4404e094
Reviewed-on: https://gerrit.libreoffice.org/9144
Reviewed-by: Michael Meeks <michael.meeks@collabora.com>
Reviewed-by: Eike Rathke <erack@redhat.com>
Tested-by: Eike Rathke <erack@redhat.com>

17 files changed, 942 insertions, 448 deletions

diff --git a/sc/inc/attarray.hxx b/sc/inc/attarray.hxx
index c4f514bf145f..8e8b8f5f765c 100644
--- a/sc/inc/attarray.hxx
+++ b/sc/inc/attarray.hxx
@@ -187,6 +187,8 @@ public:
         SCROW nStartRow, SCROW nEndRow, long nDy, ScAttrArray& rAttrArray, sal_Int16 nStripFlags = 0) const;
 
     void    DeleteHardAttr( SCROW nStartRow, SCROW nEndRow );
+
+    SCSIZE Count( SCROW nRow1, SCROW nRow2 ) const;
 };
 
 //                              Iterator for attributes
diff --git a/sc/inc/column.hxx b/sc/inc/column.hxx
index edf6acae15c1..d77fc18c3f54 100644
--- a/sc/inc/column.hxx
+++ b/sc/inc/column.hxx
@@ -174,11 +174,14 @@ public:
     const sc::CellNoteStoreType& GetCellNoteStore() const { return maCellNotes; }
 
     ScRefCellValue GetCellValue( SCROW nRow ) const;
+    ScRefCellValue GetCellValue( sc::ColumnBlockConstPosition& rBlockPos, SCROW nRow ) const;
     ScRefCellValue GetCellValue( const sc::CellStoreType::const_iterator& itPos, size_t nOffset ) const;
 
+    const sc::CellTextAttr* GetCellTextAttr( SCROW nRow ) const;
+    const sc::CellTextAttr* GetCellTextAttr( sc::ColumnBlockConstPosition& rBlockPos, SCROW nRow ) const;
+
     void        Delete( SCROW nRow );
     void        FreeAll();
-    void        SwapRow( SCROW nRow1, SCROW nRow2 );
     void        SwapCell( SCROW nRow, ScColumn& rCol);
 
     bool        HasAttrib( SCROW nRow1, SCROW nRow2, sal_uInt16 nMask ) const;
@@ -488,6 +491,7 @@ public:
             sc::CellStoreType::iterator itr);
 
     void SetScriptType( SCROW nRow, sal_uInt8 nType );
+    void UpdateScriptTypes( SCROW nRow1, SCROW nRow2 );
 
     size_t GetFormulaHash( SCROW nRow ) const;
 
@@ -503,6 +507,8 @@ public:
 
     SvtBroadcaster* GetBroadcaster( SCROW nRow );
     const SvtBroadcaster* GetBroadcaster( SCROW nRow ) const;
+    const SvtBroadcaster* GetBroadcaster( sc::ColumnBlockConstPosition& rBlockPos, SCROW nRow ) const;
+
     void DeleteBroadcasters( sc::ColumnBlockPosition& rBlockPos, SCROW nRow1, SCROW nRow2 );
     bool HasBroadcaster() const;
 
@@ -512,6 +518,7 @@ public:
     // cell notes
     ScPostIt* GetCellNote( SCROW nRow );
     const ScPostIt* GetCellNote( SCROW nRow ) const;
+    const ScPostIt* GetCellNote( sc::ColumnBlockConstPosition& rBlockPos, SCROW nRow ) const;
     void DeleteCellNotes( sc::ColumnBlockPosition& rBlockPos, SCROW nRow1, SCROW nRow2 );
     void DeleteCellNote( SCROW nRow );
     bool HasCellNotes() const;
@@ -533,7 +540,8 @@ public:
                                      SCROW nRowOffsetDest=0) const;
     void DuplicateNotes(SCROW nStartRow, size_t nDataSize, ScColumn& rDestCol,
                             sc::ColumnBlockPosition& maDestBlockPos, bool bCloneCaption = true, SCROW nRowOffsetDest=0 ) const;
-    void UpdateNoteCaptions();
+
+    void UpdateNoteCaptions( SCROW nRow1, SCROW nRow2 );
 
     void InterpretDirtyCells( SCROW nRow1, SCROW nRow2 );
 
@@ -547,6 +555,9 @@ public:
 
     void DetachFormulaCells( const sc::CellStoreType::position_type& aPos, size_t nLength );
 
+    void AttachFormulaCells( sc::StartListeningContext& rCxt, SCROW nRow1, SCROW nRow2 );
+    void DetachFormulaCells( sc::EndListeningContext& rCxt, SCROW nRow1, SCROW nRow2 );
+
     /**
      * Regroup formula cells for the entire column.
      */
@@ -556,6 +567,8 @@ public:
     void DumpFormulaGroups() const;
 #endif
 
+    SCSIZE GetPatternCount( SCROW nRow1, SCROW nRow2 ) const;
+
 private:
 
     sc::CellStoreType::iterator GetPositionToInsert( SCROW nRow );
diff --git a/sc/inc/document.hxx b/sc/inc/document.hxx
index 8c8cbf113f19..365cffdae538 100644
--- a/sc/inc/document.hxx
+++ b/sc/inc/document.hxx
@@ -1558,6 +1558,8 @@ public:
 
     SC_DLLPUBLIC bool IsManualRowHeight(SCROW nRow, SCTAB nTab) const;
 
+    bool HasUniformRowHeight( SCTAB nTab, SCROW nRow1, SCROW nRow2 ) const;
+
     /**
      * Write all column row flags to table's flag data, because not all column
      * row attributes are stored in the flag data members.  This is necessary
@@ -2044,6 +2046,7 @@ public:
 
     sal_uInt8 GetScriptType( const ScAddress& rPos ) const;
     void SetScriptType( const ScAddress& rPos, sal_uInt8 nType );
+    void UpdateScriptTypes( const ScAddress& rPos, SCCOL nColSize, SCROW nRowSize );
 
     size_t GetFormulaHash( const ScAddress& rPos ) const;
 
diff --git a/sc/inc/formulacell.hxx b/sc/inc/formulacell.hxx
index 69023a7a4cde..ff84ae4fb593 100644
--- a/sc/inc/formulacell.hxx
+++ b/sc/inc/formulacell.hxx
@@ -160,6 +160,7 @@ public:
                     ~ScFormulaCell();
 
     ScFormulaCell* Clone() const;
+    ScFormulaCell* Clone( const ScAddress& rPos ) const;
 
     ScFormulaCell( ScDocument* pDoc, const ScAddress& rPos );
 
diff --git a/sc/inc/fstalgorithm.hxx b/sc/inc/fstalgorithm.hxx
new file mode 100644
index 000000000000..08d68d4e7812
--- /dev/null
+++ b/sc/inc/fstalgorithm.hxx
@@ -0,0 +1,138 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ */
+
+#ifndef INCLUDED_SC_INC_FSTALGORITHM_HXX
+#define INCLUDED_SC_INC_FSTALGORITHM_HXX
+
+#include <mdds/flat_segment_tree.hpp>
+#include <vector>
+
+namespace sc {
+
+template<typename _Key, typename _Span>
+void buildSpan(
+    std::vector<_Span>& rSpans,
+    typename mdds::flat_segment_tree<_Key,bool>::const_iterator it,
+    typename mdds::flat_segment_tree<_Key,bool>::const_iterator itEnd, const _Key* pStart )
+{
+    _Key nLastPos = it->first;
+    bool bLastVal = it->second;
+    for (++it; it != itEnd; ++it)
+    {
+        _Key nThisPos = it->first;
+        bool bThisVal = it->second;
+
+        if (bLastVal)
+        {
+            _Key nIndex1 = nLastPos;
+            _Key nIndex2 = nThisPos-1;
+
+            if (!pStart || *pStart < nIndex1)
+                rSpans.push_back(_Span(nIndex1, nIndex2));
+            else if (*pStart <= nIndex2)
+                rSpans.push_back(_Span(*pStart, nIndex2));
+        }
+
+        nLastPos = nThisPos;
+        bLastVal = bThisVal;
+    }
+}
+
+template<typename _Key, typename _Val, typename _Span>
+void buildSpanWithValue(
+    std::vector<_Span>& rSpans,
+    typename mdds::flat_segment_tree<_Key,_Val>::const_iterator it,
+    typename mdds::flat_segment_tree<_Key,_Val>::const_iterator itEnd, const _Key* pStart )
+{
+    _Key nLastPos = it->first;
+    _Val nLastVal = it->second;
+    for (++it; it != itEnd; ++it)
+    {
+        _Key nThisPos = it->first;
+        _Val nThisVal = it->second;
+
+        if (nLastVal)
+        {
+            _Key nIndex1 = nLastPos;
+            _Key nIndex2 = nThisPos-1;
+
+            if (!pStart || *pStart < nIndex1)
+                rSpans.push_back(_Span(nIndex1, nIndex2, nLastVal));
+            else if (*pStart <= nIndex2)
+                rSpans.push_back(_Span(*pStart, nIndex2, nLastVal));
+        }
+
+        nLastPos = nThisPos;
+        nLastVal = nThisVal;
+    }
+}
+
+/**
+ * Convert a flat_segment_tree structure whose value type is boolean, into
+ * an array of ranges that corresponds with the segments that have a 'true'
+ * value.
+ */
+template<typename _Key, typename _Span>
+std::vector<_Span> toSpanArray( const mdds::flat_segment_tree<_Key,bool>& rTree )
+{
+    typedef mdds::flat_segment_tree<_Key,bool> FstType;
+
+    std::vector<_Span> aSpans;
+
+    typename FstType::const_iterator it = rTree.begin(), itEnd = rTree.end();
+    buildSpan<_Key,_Span>(aSpans, it, itEnd, NULL);
+    return aSpans;
+}
+
+/**
+ * Convert a flat_segment_tree structure into an array of ranges with
+ * values.  Only those ranges whose value is evaluated to be true will be
+ * included.  The value type must be something that supports bool operator.
+ * The span type must support a constructor that takes a start key, an end
+ * key and a value in this order.
+ */
+template<typename _Key, typename _Val, typename _Span>
+std::vector<_Span> toSpanArrayWithValue( const mdds::flat_segment_tree<_Key,_Val>& rTree )
+{
+    typedef mdds::flat_segment_tree<_Key,_Val> FstType;
+
+    std::vector<_Span> aSpans;
+
+    typename FstType::const_iterator it = rTree.begin(), itEnd = rTree.end();
+    buildSpanWithValue<_Key,_Val,_Span>(aSpans, it, itEnd, NULL);
+    return aSpans;
+}
+
+template<typename _Key, typename _Span>
+std::vector<_Span> toSpanArray( const mdds::flat_segment_tree<_Key,bool>& rTree, _Key nStartPos )
+{
+    typedef mdds::flat_segment_tree<_Key,bool> FstType;
+
+    std::vector<_Span> aSpans;
+    if (!rTree.is_tree_valid())
+        return aSpans;
+
+    bool bThisVal = false;
+    std::pair<typename FstType::const_iterator, bool> r =
+        rTree.search_tree(nStartPos, bThisVal);
+
+    if (!r.second)
+        // Tree search failed.
+        return aSpans;
+
+    typename FstType::const_iterator it = r.first, itEnd = rTree.end();
+    buildSpan<_Key,_Span>(aSpans, it, itEnd, &nStartPos);
+    return aSpans;
+}
+
+}
+
+#endif
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/inc/table.hxx b/sc/inc/table.hxx
index f6d9a32956cf..6666c9bffdf7 100644
--- a/sc/inc/table.hxx
+++ b/sc/inc/table.hxx
@@ -380,6 +380,8 @@ public:
     CellType    GetCellType( SCCOL nCol, SCROW nRow ) const;
     ScRefCellValue GetCellValue( SCCOL nCol, SCROW nRow ) const;
 
+    const sc::CellTextAttr* GetCellTextAttr( SCCOL nCol, SCROW nRow ) const;
+
     void        GetFirstDataPos(SCCOL& rCol, SCROW& rRow) const;
     void        GetLastDataPos(SCCOL& rCol, SCROW& rRow) const;
 
@@ -815,6 +817,8 @@ public:
 
     bool IsManualRowHeight(SCROW nRow) const;
 
+    bool HasUniformRowHeight( SCROW nRow1, SCROW nRow2 ) const;
+
     void        SyncColRowFlags();
 
     void        StripHidden( SCCOL& rX1, SCROW& rY1, SCCOL& rX2, SCROW& rY2 );
@@ -864,6 +868,7 @@ public:
 
     sal_uInt8 GetScriptType( SCCOL nCol, SCROW nRow ) const;
     void SetScriptType( SCCOL nCol, SCROW nRow, sal_uInt8 nType );
+    void UpdateScriptTypes( SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2 );
 
     sal_uInt8 GetRangeScriptType( sc::ColumnBlockPosition& rBlockPos, SCCOL nCol, SCROW nRow1, SCROW nRow2 );
 
@@ -983,16 +988,16 @@ private:
     bool        IsSorted(SCCOLROW nStart, SCCOLROW nEnd) const;
     void        DecoladeRow( ScSortInfoArray*, SCROW nRow1, SCROW nRow2 );
     void        SwapCol(SCCOL nCol1, SCCOL nCol2);
-    void        SwapRow(SCROW nRow1, SCROW nRow2);
     short CompareCell(
         sal_uInt16 nSort,
         ScRefCellValue& rCell1, SCCOL nCell1Col, SCROW nCell1Row,
         ScRefCellValue& rCell2, SCCOL nCell2Col, SCROW nCell2Row ) const;
     short       Compare(SCCOLROW nIndex1, SCCOLROW nIndex2) const;
     short       Compare( ScSortInfoArray*, SCCOLROW nIndex1, SCCOLROW nIndex2) const;
-    ScSortInfoArray*    CreateSortInfoArray( SCCOLROW nInd1, SCCOLROW nInd2 );
+    ScSortInfoArray* CreateSortInfoArray( SCCOLROW nInd1, SCCOLROW nInd2, bool bKeepQuery );
     void        QuickSort( ScSortInfoArray*, SCsCOLROW nLo, SCsCOLROW nHi);
-    void        SortReorder( ScSortInfoArray*, ScProgress* );
+    void SortReorder( ScSortInfoArray* pArray, ScProgress* pProgress );
+    void SortReorderByRow( ScSortInfoArray* pArray, ScProgress* pProgress );
 
     bool        CreateExcelQuery(SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2, ScQueryParam& rQueryParam);
     bool        CreateStarQuery(SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2, ScQueryParam& rQueryParam);
@@ -1021,6 +1026,9 @@ private:
     void EndListening( sc::EndListeningContext& rCxt, SCCOL nCol, SCROW nRow, SvtListener& rListener );
     void        StartAllListeners();
 
+    void AttachFormulaCells( sc::StartListeningContext& rCxt, SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2 );
+    void DetachFormulaCells( sc::EndListeningContext& rCxt, SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2 );
+
     void        SetLoadingMedium(bool bLoading);
 
     SCSIZE      FillMaxRot( RowInfo* pRowInfo, SCSIZE nArrCount, SCCOL nX1, SCCOL nX2,
diff --git a/sc/source/core/data/attarray.cxx b/sc/source/core/data/attarray.cxx
index cee38bb8823d..16113db0029a 100644
--- a/sc/source/core/data/attarray.cxx
+++ b/sc/source/core/data/attarray.cxx
@@ -2203,6 +2203,18 @@ void ScAttrArray::DeleteHardAttr(SCROW nStartRow, SCROW nEndRow)
     }
 }
 
+SCSIZE ScAttrArray::Count( SCROW nStartRow, SCROW nEndRow ) const
+{
+    SCSIZE  nIndex1, nIndex2;
+
+    if( !Search( nStartRow, nIndex1 ) )
+        return 0;
+
+    if( !Search( nEndRow, nIndex2 ) )
+        nIndex2 = nCount - 1;
+
+    return nIndex2 - nIndex1 + 1;
+}
 
 // move within a document
 
diff --git a/sc/source/core/data/column.cxx b/sc/source/core/data/column.cxx
index a4a38dff30c5..9ff510ccb133 100644
--- a/sc/source/core/data/column.cxx
+++ b/sc/source/core/data/column.cxx
@@ -770,6 +770,16 @@ ScRefCellValue ScColumn::GetCellValue( SCROW nRow ) const
     return GetCellValue(aPos.first, aPos.second);
 }
 
+ScRefCellValue ScColumn::GetCellValue( sc::ColumnBlockConstPosition& rBlockPos, SCROW nRow ) const
+{
+    std::pair<sc::CellStoreType::const_iterator,size_t> aPos = maCells.position(rBlockPos.miCellPos, nRow);
+    if (aPos.first == maCells.end())
+        return ScRefCellValue();
+
+    rBlockPos.miCellPos = aPos.first; // Store this for next call.
+    return GetCellValue(aPos.first, aPos.second);
+}
+
 ScRefCellValue ScColumn::GetCellValue( const sc::CellStoreType::const_iterator& itPos, size_t nOffset ) const
 {
     ScRefCellValue aVal; // Defaults to empty cell.
@@ -802,329 +812,30 @@ ScRefCellValue ScColumn::GetCellValue( const sc::CellStoreType::const_iterator&
     return aVal;
 }
 
-namespace {
-
-ScFormulaCell* cloneFormulaCell(ScDocument* pDoc, const ScAddress& rNewPos, ScFormulaCell& rOldCell)
+const sc::CellTextAttr* ScColumn::GetCellTextAttr( SCROW nRow ) const
 {
-    ScFormulaCell* pNew = new ScFormulaCell(rOldCell, *pDoc, rNewPos, SC_CLONECELL_ADJUST3DREL);
-    rOldCell.EndListeningTo(pDoc);
-    pNew->StartListeningTo(pDoc);
-    pNew->SetDirty();
-    return pNew;
-}
+    sc::CellTextAttrStoreType::const_position_type aPos = maCellTextAttrs.position(nRow);
+    if (aPos.first == maCellTextAttrs.end())
+        return NULL;
+
+    if (aPos.first->type != sc::element_type_celltextattr)
+        return NULL;
 
+    return &sc::celltextattr_block::at(*aPos.first->data, aPos.second);
 }
 
-void ScColumn::SwapRow(SCROW nRow1, SCROW nRow2)
+const sc::CellTextAttr* ScColumn::GetCellTextAttr( sc::ColumnBlockConstPosition& rBlockPos, SCROW nRow ) const
 {
-    if (nRow1 == nRow2)
-        // Nothing to swap.
-        return;
-
-    // Ensure that nRow1 < nRow2.
-    if (nRow2 < nRow1)
-        std::swap(nRow1, nRow2);
-
-    // Broadcasters (if exist) should NOT be swapped.
-
-    sc::CellStoreType::position_type aPos1 = maCells.position(nRow1);
-    if (aPos1.first == maCells.end())
-        return;
-
-    sc::CellStoreType::position_type aPos2 = maCells.position(aPos1.first, nRow2);
-    if (aPos2.first == maCells.end())
-        return;
-
-    std::vector<SCROW> aRows;
-    aRows.reserve(2);
-    aRows.push_back(nRow1);
-    aRows.push_back(nRow2);
-
-    sc::CellStoreType::iterator it1 = aPos1.first, it2 = aPos2.first;
-
-    if (it1->type == it2->type)
-    {
-        // Both positions are of the same type. Do a simple value swap.
-        switch (it1->type)
-        {
-            case sc::element_type_empty:
-                // Both are empty. Nothing to swap.
-                return;
-            case sc::element_type_numeric:
-                std::swap(
-                    sc::numeric_block::at(*it1->data, aPos1.second),
-                    sc::numeric_block::at(*it2->data, aPos2.second));
-            break;
-            case sc::element_type_string:
-                std::swap(
-                    sc::string_block::at(*it1->data, aPos1.second),
-                    sc::string_block::at(*it2->data, aPos2.second));
-            break;
-            case sc::element_type_edittext:
-                std::swap(
-                    sc::edittext_block::at(*it1->data, aPos1.second),
-                    sc::edittext_block::at(*it2->data, aPos2.second));
-            break;
-            case sc::element_type_formula:
-            {
-                // Swapping of formula cells involve adjustment of references wrt their positions.
-                sc::formula_block::iterator itf1 = sc::formula_block::begin(*it1->data);
-                sc::formula_block::iterator itf2 = sc::formula_block::begin(*it2->data);
-                std::advance(itf1, aPos1.second);
-                std::advance(itf2, aPos2.second);
-
-                // TODO: Find out a way to adjust references without cloning new instances.
-                boost::scoped_ptr<ScFormulaCell> pOld1(*itf1);
-                boost::scoped_ptr<ScFormulaCell> pOld2(*itf2);
-                DetachFormulaCell(aPos1, **itf1);
-                DetachFormulaCell(aPos2, **itf2);
-                ScFormulaCell* pNew1 = cloneFormulaCell(pDocument, ScAddress(nCol, nRow1, nTab), *pOld2);
-                ScFormulaCell* pNew2 = cloneFormulaCell(pDocument, ScAddress(nCol, nRow2, nTab), *pOld1);
-                *itf1 = pNew1;
-                *itf2 = pNew2;
-
-                ActivateNewFormulaCell(aPos1, *pNew1);
-                ActivateNewFormulaCell(aPos2, *pNew2);
-            }
-            break;
-            default:
-                ;
-        }
-
-        SwapCellTextAttrs(nRow1, nRow2);
-        SwapCellNotes(nRow1, nRow2);
-        CellStorageModified();
-        BroadcastCells(aRows, SC_HINT_DATACHANGED);
-        return;
-    }
-
-    // The two cells are of different types.
-
-    ScRefCellValue aCell1 = GetCellValue(aPos1.first, aPos1.second);
-    ScRefCellValue aCell2 = GetCellValue(aPos2.first, aPos2.second);
-
-    // Make sure to put cells in row 1 first then row 2!
-
-    if (aCell1.meType == CELLTYPE_NONE)
-    {
-        // cell 1 is empty and cell 2 is not.
-        switch (aCell2.meType)
-        {
-            case CELLTYPE_VALUE:
-                it1 = maCells.set(it1, nRow1, aCell2.mfValue); // it2 becomes invalid.
-                maCells.set_empty(it1, nRow2, nRow2);
-            break;
-            case CELLTYPE_STRING:
-                it1 = maCells.set(it1, nRow1, *aCell2.mpString);
-                maCells.set_empty(it1, nRow2, nRow2);
-            break;
-            case CELLTYPE_EDIT:
-            {
-                it1 = maCells.set(
-                    it1, nRow1, const_cast<EditTextObject*>(aCell2.mpEditText));
-                EditTextObject* p;
-                maCells.release(it1, nRow2, p);
-            }
-            break;
-            case CELLTYPE_FORMULA:
-            {
-                // cell 1 is empty and cell 2 is a formula cell.
-                ScFormulaCell* pNew = cloneFormulaCell(pDocument, ScAddress(nCol, nRow1, nTab), *aCell2.mpFormula);
-                DetachFormulaCell(aPos2, *aCell2.mpFormula);
-                it1 = maCells.set(it1, nRow1, pNew);
-                maCells.set_empty(it1, nRow2, nRow2); // original formula cell gets deleted.
-                ActivateNewFormulaCell(it1, nRow1, *pNew);
-            }
-            break;
-            default:
-                ;
-        }
-
-        SwapCellTextAttrs(nRow1, nRow2);
-        SwapCellNotes(nRow1, nRow2);
-        CellStorageModified();
-        BroadcastCells(aRows, SC_HINT_DATACHANGED);
-        return;
-    }
-
-    if (aCell2.meType == CELLTYPE_NONE)
-    {
-        // cell 1 is not empty and cell 2 is empty.
-        switch (aCell1.meType)
-        {
-            case CELLTYPE_VALUE:
-                // Value is copied in Cell1.
-                it1 = maCells.set_empty(it1, nRow1, nRow1);
-                maCells.set(it1, nRow2, aCell1.mfValue);
-            break;
-            case CELLTYPE_STRING:
-            {
-                svl::SharedString aStr = *aCell1.mpString; // make a copy.
-                it1 = maCells.set_empty(it1, nRow1, nRow1); // original string is gone.
-                maCells.set(it1, nRow2, aStr);
-            }
-            break;
-            case CELLTYPE_EDIT:
-            {
-                EditTextObject* p;
-                it1 = maCells.release(it1, nRow1, p);
-                maCells.set(it1, nRow2, p);
-            }
-            break;
-            case CELLTYPE_FORMULA:
-            {
-                // cell 1 is a formula cell and cell 2 is empty.
-                ScFormulaCell* pNew = cloneFormulaCell(pDocument, ScAddress(nCol, nRow2, nTab), *aCell1.mpFormula);
-                DetachFormulaCell(aPos1, *aCell1.mpFormula);
-                it1 = maCells.set_empty(it1, nRow1, nRow1); // original formula cell is gone.
-                it1 = maCells.set(it1, nRow2, pNew);
-                ActivateNewFormulaCell(it1, nRow2, *pNew);
-            }
-            break;
-            default:
-                ;
-        }
-
-        SwapCellTextAttrs(nRow1, nRow2);
-        SwapCellNotes(nRow1, nRow2);
-        CellStorageModified();
-        BroadcastCells(aRows, SC_HINT_DATACHANGED);
-        return;
-    }
-
-    // Neither cells are empty, and they are of different types.
-    switch (aCell1.meType)
-    {
-        case CELLTYPE_VALUE:
-        {
-            switch (aCell2.meType)
-            {
-                case CELLTYPE_STRING:
-                    it1 = maCells.set(it1, nRow1, *aCell2.mpString);
-                break;
-                case CELLTYPE_EDIT:
-                {
-                    it1 = maCells.set(
-                        it1, nRow1, const_cast<EditTextObject*>(aCell2.mpEditText));
-                    EditTextObject* p;
-                    it1 = maCells.release(it1, nRow2, p);
-                }
-                break;
-                case CELLTYPE_FORMULA:
-                {
-                    DetachFormulaCell(aPos2, *aCell2.mpFormula);
-                    ScFormulaCell* pNew = cloneFormulaCell(pDocument, ScAddress(nCol, nRow1, nTab), *aCell2.mpFormula);
-                    it1 = maCells.set(it1, nRow1, pNew);
-                    ActivateNewFormulaCell(it1, nRow1, *pNew);
-                    // The old formula cell will get overwritten below.
-                }
-                break;
-                default:
-                    ;
-            }
-
-            maCells.set(it1, nRow2, aCell1.mfValue);
-
-        }
-        break;
-        case CELLTYPE_STRING:
-        {
-            svl::SharedString aStr = *aCell1.mpString; // make a copy.
-            switch (aCell2.meType)
-            {
-                case CELLTYPE_VALUE:
-                    it1 = maCells.set(it1, nRow1, aCell2.mfValue);
-                break;
-                case CELLTYPE_EDIT:
-                {
-                    it1 = maCells.set(
-                        it1, nRow1, const_cast<EditTextObject*>(aCell2.mpEditText));
-                    EditTextObject* p;
-                    it1 = maCells.release(it1, nRow2, p); // prevent it being overwritten.
-                }
-                break;
-                case CELLTYPE_FORMULA:
-                {
-                    // cell 1 - string, cell 2 - formula
-                    DetachFormulaCell(aPos2, *aCell2.mpFormula);
-                    ScFormulaCell* pNew = cloneFormulaCell(pDocument, ScAddress(nCol, nRow1, nTab), *aCell2.mpFormula);
-                    it1 = maCells.set(it1, nRow1, pNew);
-                    ActivateNewFormulaCell(it1, nRow1, *pNew);
-                    // Old formula cell will get overwritten below.
-                }
-                break;
-                default:
-                    ;
-            }
-
-            maCells.set(it1, nRow2, aStr);
-        }
-        break;
-        case CELLTYPE_EDIT:
-        {
-            EditTextObject* p;
-            it1 = maCells.release(it1, nRow1, p);
-
-            switch (aCell2.meType)
-            {
-                case CELLTYPE_VALUE:
-                    it1 = maCells.set(it1, nRow1, aCell2.mfValue);
-                break;
-                case CELLTYPE_STRING:
-                    it1 = maCells.set(it1, nRow1, *aCell2.mpString);
-                break;
-                case CELLTYPE_FORMULA:
-                {
-                    DetachFormulaCell(aPos2, *aCell2.mpFormula);
-                    ScFormulaCell* pNew = cloneFormulaCell(pDocument, ScAddress(nCol, nRow1, nTab), *aCell2.mpFormula);
-                    it1 = maCells.set(it1, nRow1, pNew);
-                    ActivateNewFormulaCell(it1, nRow1, *pNew);
-                    // Old formula cell will get overwritten below.
-                }
-                break;
-                default:
-                    ;
-            }
+    sc::CellTextAttrStoreType::const_position_type aPos = maCellTextAttrs.position(rBlockPos.miCellTextAttrPos, nRow);
+    if (aPos.first == maCellTextAttrs.end())
+        return NULL;
 
-            maCells.set(it1, nRow2, const_cast<EditTextObject*>(aCell1.mpEditText));
-        }
-        break;
-        case CELLTYPE_FORMULA:
-        {
-            // cell 1 is a formula cell and cell 2 is not.
-            DetachFormulaCell(aPos1, *aCell1.mpFormula);
-            ScFormulaCell* pNew = cloneFormulaCell(pDocument, ScAddress(nCol, nRow2, nTab), *aCell1.mpFormula);
-            switch (aCell2.meType)
-            {
-                case CELLTYPE_VALUE:
-                    it1 = maCells.set(it1, nRow1, aCell2.mfValue);
-                break;
-                case CELLTYPE_STRING:
-                    it1 = maCells.set(it1, nRow1, *aCell2.mpString);
-                break;
-                case CELLTYPE_EDIT:
-                {
-                    it1 = maCells.set(it1, nRow1, aCell2.mpEditText);
-                    EditTextObject* p;
-                    it1 = maCells.release(it1, nRow2, p);
-                }
-                break;
-                default:
-                    ;
-            }
+    rBlockPos.miCellTextAttrPos = aPos.first;
 
-            it1 = maCells.set(it1, nRow2, pNew);
-            ActivateNewFormulaCell(it1, nRow2, *pNew);
-        }
-        break;
-        default:
-            ;
-    }
+    if (aPos.first->type != sc::element_type_celltextattr)
+        return NULL;
 
-    SwapCellTextAttrs(nRow1, nRow2);
-    SwapCellNotes(nRow1, nRow2);
-    CellStorageModified();
-    BroadcastCells(aRows, SC_HINT_DATACHANGED);
+    return &sc::celltextattr_block::at(*aPos.first->data, aPos.second);
 }
 
 namespace {
@@ -2190,34 +1901,25 @@ void resetColumnPosition(sc::CellStoreType& rCells, SCCOL nCol)
     }
 }
 
-}
-
-void ScColumn::UpdateNoteCaptions()
+class NoteCaptionUpdater
 {
-    sc::CellNoteStoreType::const_iterator itBlk = maCellNotes.begin(), itBlkEnd = maCellNotes.end();
-    sc::cellnote_block::const_iterator itData, itDataEnd;
+    SCCOL mnCol;
+    SCTAB mnTab;
+public:
+    NoteCaptionUpdater( SCCOL nCol, SCTAB nTab ) : mnCol(nCol), mnTab(nTab) {}
 
-    SCROW curRow = 0;
-    for (;itBlk!=itBlkEnd;++itBlk)
+    void operator() ( size_t nRow, ScPostIt* p )
     {
-        if (itBlk->data)
-        {
-            // non empty block
-            itData = sc::cellnote_block::begin(*itBlk->data);
-            itDataEnd = sc::cellnote_block::end(*itBlk->data);
-            for(;itData!=itDataEnd; ++itData)
-            {
-                ScPostIt* pNote = *itData;
-                pNote->UpdateCaptionPos(ScAddress(nCol, curRow, nTab));
-                curRow +=1;
-            }
-        }
-        else
-        {
-            // empty block
-            curRow += itBlk->size;
-        }
+        p->UpdateCaptionPos(ScAddress(mnCol,nRow,mnTab));
     }
+};
+
+}
+
+void ScColumn::UpdateNoteCaptions( SCROW nRow1, SCROW nRow2 )
+{
+    NoteCaptionUpdater aFunc(nCol, nTab);
+    sc::ProcessNote(maCellNotes.begin(), maCellNotes, nRow1, nRow2, aFunc);
 }
 
 void ScColumn::SwapCol(ScColumn& rCol)
@@ -2228,8 +1930,8 @@ void ScColumn::SwapCol(ScColumn& rCol)
     maCellNotes.swap(rCol.maCellNotes);
 
     // notes update caption
-    UpdateNoteCaptions();
-    rCol.UpdateNoteCaptions();
+    UpdateNoteCaptions(0, MAXROW);
+    rCol.UpdateNoteCaptions(0, MAXROW);
 
     ScAttrArray* pTempAttr = rCol.pAttrArray;
     rCol.pAttrArray = pAttrArray;
@@ -2278,7 +1980,7 @@ void ScColumn::MoveTo(SCROW nStartRow, SCROW nEndRow, ScColumn& rCol)
 
     // move the notes to the destination column
     maCellNotes.transfer(nStartRow, nEndRow, rCol.maCellNotes, nStartRow);
-    UpdateNoteCaptions();
+    UpdateNoteCaptions(0, MAXROW);
 
     // Re-group transferred formula cells.
     aPos = rCol.maCells.position(nStartRow);
diff --git a/sc/source/core/data/column2.cxx b/sc/source/core/data/column2.cxx
index 465ae23f5f1e..3fdbc52c88f3 100644
--- a/sc/source/core/data/column2.cxx
+++ b/sc/source/core/data/column2.cxx
@@ -1726,6 +1726,11 @@ void ScColumn::DumpFormulaGroups() const
 }
 #endif
 
+SCSIZE ScColumn::GetPatternCount( SCROW nRow1, SCROW nRow2 ) const
+{
+    return pAttrArray ? pAttrArray->Count(nRow1, nRow2) : 0;
+}
+
 void ScColumn::CopyCellTextAttrsToDocument(SCROW nRow1, SCROW nRow2, ScColumn& rDestCol) const
 {
     rDestCol.maCellTextAttrs.set_empty(nRow1, nRow2); // Empty the destination range first.
@@ -1956,6 +1961,17 @@ const SvtBroadcaster* ScColumn::GetBroadcaster(SCROW nRow) const
     return maBroadcasters.get<SvtBroadcaster*>(nRow);
 }
 
+const SvtBroadcaster* ScColumn::GetBroadcaster( sc::ColumnBlockConstPosition& rBlockPos, SCROW nRow ) const
+{
+    sc::BroadcasterStoreType::const_position_type aPos = maBroadcasters.position(rBlockPos.miBroadcasterPos, nRow);
+    rBlockPos.miBroadcasterPos = aPos.first;
+
+    if (aPos.first->type != sc::element_type_broadcaster)
+        return NULL;
+
+    return sc::broadcaster_block::at(*aPos.first->data, aPos.second);
+}
+
 void ScColumn::DeleteBroadcasters( sc::ColumnBlockPosition& rBlockPos, SCROW nRow1, SCROW nRow2 )
 {
     rBlockPos.miBroadcasterPos =
@@ -1984,6 +2000,17 @@ const ScPostIt* ScColumn::GetCellNote(SCROW nRow) const
     return maCellNotes.get<ScPostIt*>(nRow);
 }
 
+const ScPostIt* ScColumn::GetCellNote( sc::ColumnBlockConstPosition& rBlockPos, SCROW nRow ) const
+{
+    sc::CellNoteStoreType::const_position_type aPos = maCellNotes.position(rBlockPos.miCellNotePos, nRow);
+    rBlockPos.miCellNotePos = aPos.first;
+
+    if (aPos.first->type != sc::element_type_cellnote)
+        return NULL;
+
+    return sc::cellnote_block::at(*aPos.first->data, aPos.second);
+}
+
 void ScColumn::SetCellNote(SCROW nRow, ScPostIt* pNote)
 {
     //pNote->UpdateCaptionPos(ScAddress(nCol, nRow, nTab)); // TODO notes usefull ? slow import with many notes
diff --git a/sc/source/core/data/column3.cxx b/sc/source/core/data/column3.cxx
index 192efcbbb979..8dcf20e7ce89 100644
--- a/sc/source/core/data/column3.cxx
+++ b/sc/source/core/data/column3.cxx
@@ -340,15 +340,35 @@ void ScColumn::DetachFormulaCell(
 
 namespace {
 
+class AttachFormulaCellsHandler
+{
+    sc::StartListeningContext& mrCxt;
+
+public:
+    AttachFormulaCellsHandler( sc::StartListeningContext& rCxt ) :
+        mrCxt(rCxt) {}
+
+    void operator() (size_t /*nRow*/, ScFormulaCell* pCell)
+    {
+        pCell->StartListeningTo(mrCxt);
+    }
+};
+
 class DetachFormulaCellsHandler
 {
     ScDocument* mpDoc;
+    sc::EndListeningContext* mpCxt;
+
 public:
-    DetachFormulaCellsHandler(ScDocument* pDoc) : mpDoc(pDoc) {}
+    DetachFormulaCellsHandler( ScDocument* pDoc, sc::EndListeningContext* pCxt ) :
+        mpDoc(pDoc), mpCxt(pCxt) {}
 
     void operator() (size_t /*nRow*/, ScFormulaCell* pCell)
     {
-        pCell->EndListeningTo(mpDoc);
+        if (mpCxt)
+            pCell->EndListeningTo(*mpCxt);
+        else
+            pCell->EndListeningTo(mpDoc);
     }
 };
 
@@ -370,10 +390,49 @@ void ScColumn::DetachFormulaCells(
     if (pDocument->IsClipOrUndo())
         return;
 
-    DetachFormulaCellsHandler aFunc(pDocument);
+    DetachFormulaCellsHandler aFunc(pDocument, NULL);
     sc::ProcessFormula(aPos.first, maCells, nRow, nNextTopRow-1, aFunc);
 }
 
+void ScColumn::AttachFormulaCells( sc::StartListeningContext& rCxt, SCROW nRow1, SCROW nRow2 )
+{
+    sc::CellStoreType::position_type aPos = maCells.position(nRow1);
+    sc::CellStoreType::iterator it = aPos.first;
+
+    sc::SharedFormulaUtil::joinFormulaCellAbove(aPos);
+    if (ValidRow(nRow2+1))
+    {
+        aPos = maCells.position(it, nRow2+1);
+        sc::SharedFormulaUtil::joinFormulaCellAbove(aPos);
+    }
+
+    if (pDocument->IsClipOrUndo())
+        return;
+
+    AttachFormulaCellsHandler aFunc(rCxt);
+    sc::ProcessFormula(it, maCells, nRow1, nRow2, aFunc);
+}
+
+void ScColumn::DetachFormulaCells( sc::EndListeningContext& rCxt, SCROW nRow1, SCROW nRow2 )
+{
+    sc::CellStoreType::position_type aPos = maCells.position(nRow1);
+    sc::CellStoreType::iterator it = aPos.first;
+
+    // Split formula grouping at the top and bottom boundaries.
+    sc::SharedFormulaUtil::splitFormulaCellGroup(aPos);
+    if (ValidRow(nRow2+1))
+    {
+        aPos = maCells.position(it, nRow2+1);
+        sc::SharedFormulaUtil::splitFormulaCellGroup(aPos);
+    }
+
+    if (pDocument->IsClipOrUndo())
+        return;
+
+    DetachFormulaCellsHandler aFunc(pDocument, &rCxt);
+    sc::ProcessFormula(it, maCells, nRow1, nRow2, aFunc);
+}
+
 sc::CellStoreType::iterator ScColumn::GetPositionToInsert( const sc::CellStoreType::iterator& it, SCROW nRow )
 {
     // See if we are overwriting an existing formula cell.
diff --git a/sc/source/core/data/column4.cxx b/sc/source/core/data/column4.cxx
index aca38b7e69ae..1855278795b2 100644
--- a/sc/source/core/data/column4.cxx
+++ b/sc/source/core/data/column4.cxx
@@ -24,6 +24,9 @@
 #include <conditio.hxx>
 #include <formulagroup.hxx>
 #include <tokenarray.hxx>
+#include <globalnames.hxx>
+#include <scitems.hxx>
+#include <cellform.hxx>
 
 #include <svl/sharedstringpool.hxx>
 
@@ -278,4 +281,105 @@ void ScColumn::PostprocessRangeNameUpdate( sc::CompileFormulaContext& rCompileCx
     std::for_each(aGroups.begin(), aGroups.end(), aFunc);
 }
 
+namespace {
+
+class ScriptTypeUpdater
+{
+    ScColumn& mrCol;
+    sc::CellTextAttrStoreType& mrTextAttrs;
+    sc::CellTextAttrStoreType::iterator miPosAttr;
+    ScConditionalFormatList* mpCFList;
+    SvNumberFormatter* mpFormatter;
+    ScAddress maPos;
+    bool mbUpdated;
+
+private:
+    void updateScriptType( size_t nRow, ScRefCellValue& rCell )
+    {
+        sc::CellTextAttrStoreType::position_type aAttrPos = mrTextAttrs.position(miPosAttr, nRow);
+        miPosAttr = aAttrPos.first;
+
+        if (aAttrPos.first->type != sc::element_type_celltextattr)
+            return;
+
+        sc::CellTextAttr& rAttr = sc::celltextattr_block::at(*aAttrPos.first->data, aAttrPos.second);
+        if (rAttr.mnScriptType != SC_SCRIPTTYPE_UNKNOWN)
+            // Script type already deteremined.  Skip it.
+            return;
+
+        const ScPatternAttr* pPat = mrCol.GetPattern(nRow);
+        if (!pPat)
+            // In theory this should never return NULL. But let's be safe.
+            return;
+
+        const SfxItemSet* pCondSet = NULL;
+        if (mpCFList)
+        {
+            maPos.SetRow(nRow);
+            const ScCondFormatItem& rItem =
+                static_cast<const ScCondFormatItem&>(pPat->GetItem(ATTR_CONDITIONAL));
+            const std::vector<sal_uInt32>& rData = rItem.GetCondFormatData();
+            pCondSet = mrCol.GetDoc().GetCondResult(rCell, maPos, *mpCFList, rData);
+        }
+
+        OUString aStr;
+        Color* pColor;
+        sal_uLong nFormat = pPat->GetNumberFormat(mpFormatter, pCondSet);
+        ScCellFormat::GetString(rCell, nFormat, aStr, &pColor, *mpFormatter, &mrCol.GetDoc());
+
+        rAttr.mnScriptType = mrCol.GetDoc().GetStringScriptType(aStr);
+        mbUpdated = true;
+    }
+
+public:
+    ScriptTypeUpdater( ScColumn& rCol ) :
+        mrCol(rCol),
+        mrTextAttrs(rCol.GetCellAttrStore()),
+        miPosAttr(mrTextAttrs.begin()),
+        mpCFList(rCol.GetDoc().GetCondFormList(rCol.GetTab())),
+        mpFormatter(rCol.GetDoc().GetFormatTable()),
+        maPos(rCol.GetCol(), 0, rCol.GetTab()),
+        mbUpdated(false)
+    {}
+
+    void operator() ( size_t nRow, double fVal )
+    {
+        ScRefCellValue aCell(fVal);
+        updateScriptType(nRow, aCell);
+    }
+
+    void operator() ( size_t nRow, const svl::SharedString& rStr )
+    {
+        ScRefCellValue aCell(&rStr);
+        updateScriptType(nRow, aCell);
+    }
+
+    void operator() ( size_t nRow, const EditTextObject* pText )
+    {
+        ScRefCellValue aCell(pText);
+        updateScriptType(nRow, aCell);
+    }
+
+    void operator() ( size_t nRow, const ScFormulaCell* pCell )
+    {
+        ScRefCellValue aCell(const_cast<ScFormulaCell*>(pCell));
+        updateScriptType(nRow, aCell);
+    }
+
+    bool isUpdated() const { return mbUpdated; }
+};
+
+}
+
+void ScColumn::UpdateScriptTypes( SCROW nRow1, SCROW nRow2 )
+{
+    if (!ValidRow(nRow1) || !ValidRow(nRow2) || nRow1 > nRow2)
+        return;
+
+    ScriptTypeUpdater aFunc(*this);
+    sc::ParseAllNonEmpty(maCells.begin(), maCells, nRow1, nRow2, aFunc);
+    if (aFunc.isUpdated())
+        CellStorageModified();
+}
+
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/source/core/data/document10.cxx b/sc/source/core/data/document10.cxx
index 823f9929da9f..0c9e7edd45a5 100644
--- a/sc/source/core/data/document10.cxx
+++ b/sc/source/core/data/document10.cxx
@@ -74,4 +74,22 @@ void ScDocument::SharePooledResources( ScDocument* pSrcDoc )
     mpCellStringPool = pSrcDoc->mpCellStringPool;
 }
 
+void ScDocument::UpdateScriptTypes( const ScAddress& rPos, SCCOL nColSize, SCROW nRowSize )
+{
+    ScTable* pTab = FetchTable(rPos.Tab());
+    if (!pTab)
+        return;
+
+    pTab->UpdateScriptTypes(rPos.Col(), rPos.Row(), rPos.Col()+nColSize-1, rPos.Row()+nRowSize-1);
+}
+
+bool ScDocument::HasUniformRowHeight( SCTAB nTab, SCROW nRow1, SCROW nRow2 ) const
+{
+    const ScTable* pTab = FetchTable(nTab);
+    if (!pTab)
+        return false;
+
+    return pTab->HasUniformRowHeight(nRow1, nRow2);
+}
+
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/source/core/data/formulacell.cxx b/sc/source/core/data/formulacell.cxx
index b96d0ad532b4..7250746c60ea 100644
--- a/sc/source/core/data/formulacell.cxx
+++ b/sc/source/core/data/formulacell.cxx
@@ -837,6 +837,11 @@ ScFormulaCell* ScFormulaCell::Clone() const
     return new ScFormulaCell(*this, *pDocument, aPos);
 }
 
+ScFormulaCell* ScFormulaCell::Clone( const ScAddress& rPos ) const
+{
+    return new ScFormulaCell(*this, *pDocument, rPos);
+}
+
 size_t ScFormulaCell::GetHash() const
 {
     return pCode->GetHash();
diff --git a/sc/source/core/data/table2.cxx b/sc/source/core/data/table2.cxx
index 2835496a4df0..b858a1c7404a 100644
--- a/sc/source/core/data/table2.cxx
+++ b/sc/source/core/data/table2.cxx
@@ -1029,6 +1029,19 @@ void ScTable::StartAllListeners()
         aCol[i].StartAllListeners();
 }
 
+void ScTable::AttachFormulaCells(
+    sc::StartListeningContext& rCxt, SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2 )
+{
+    for (SCCOL nCol = nCol1; nCol <= nCol2; ++nCol)
+        aCol[nCol].AttachFormulaCells(rCxt, nRow1, nRow2);
+}
+
+void ScTable::DetachFormulaCells(
+    sc::EndListeningContext& rCxt, SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2 )
+{
+    for (SCCOL nCol = nCol1; nCol <= nCol2; ++nCol)
+        aCol[nCol].DetachFormulaCells(rCxt, nRow1, nRow2);
+}
 
 void ScTable::StartNeededListeners()
 {
@@ -1587,6 +1600,14 @@ ScRefCellValue ScTable::GetCellValue( SCCOL nCol, SCROW nRow ) const
     return aCol[nCol].GetCellValue(nRow);
 }
 
+const sc::CellTextAttr* ScTable::GetCellTextAttr( SCCOL nCol, SCROW nRow ) const
+{
+    if (!ValidColRow(nCol, nRow))
+        return NULL;
+
+    return aCol[nCol].GetCellTextAttr(nRow);
+}
+
 void ScTable::GetFirstDataPos(SCCOL& rCol, SCROW& rRow) const
 {
     rCol = 0;
diff --git a/sc/source/core/data/table3.cxx b/sc/source/core/data/table3.cxx
index 16ed68dd7de6..429cd52ede92 100644
--- a/sc/source/core/data/table3.cxx
+++ b/sc/source/core/data/table3.cxx
@@ -56,11 +56,19 @@
 #include "tokenarray.hxx"
 #include "mtvcellfunc.hxx"
 #include "columnspanset.hxx"
+#include <stlalgorithm.hxx>
+#include <fstalgorithm.hxx>
+#include <listenercontext.hxx>
+#include <sharedformula.hxx>
 
 #include "svl/sharedstringpool.hxx"
 
 #include <vector>
+#include <boost/scoped_ptr.hpp>
 #include <boost/unordered_set.hpp>
+#include <boost/noncopyable.hpp>
+#include <boost/ptr_container/ptr_vector.hpp>
+#include <mdds/flat_segment_tree.hpp>
 
 using namespace ::com::sun::star;
 
@@ -212,78 +220,186 @@ IMPL_FIXEDMEMPOOL_NEWDEL( ScSortInfo )
 // END OF STATIC DATA -----------------------------------------------------
 
 
-class ScSortInfoArray
+class ScSortInfoArray : boost::noncopyable
 {
+public:
+
+    struct Cell
+    {
+        ScRefCellValue maCell;
+        const sc::CellTextAttr* mpAttr;
+        const SvtBroadcaster* mpBroadcaster;
+        const ScPostIt* mpNote;
+        const ScPatternAttr* mpPattern;
+
+        Cell() : mpAttr(NULL), mpBroadcaster(NULL), mpNote(NULL), mpPattern(NULL) {}
+    };
+
+    struct Row
+    {
+        std::vector<Cell> maCells;
+
+        bool mbHidden:1;
+        bool mbFiltered:1;
+
+        Row( size_t nColSize ) : maCells(nColSize, Cell()), mbHidden(false), mbFiltered(false) {}
+    };
+
+    typedef std::vector<Row*> RowsType;
+
 private:
+    boost::scoped_ptr<RowsType> mpRows; /// row-wise data table for sort by row operation.
+
     ScSortInfo***   pppInfo;
     SCSIZE          nCount;
     SCCOLROW        nStart;
+    SCCOLROW        mnLastIndex; /// index of last non-empty cell position.
     sal_uInt16      nUsedSorts;
 
+    bool mbKeepQuery;
+
 public:
-                ScSortInfoArray( sal_uInt16 nSorts, SCCOLROW nInd1, SCCOLROW nInd2 ) :
-                        pppInfo( new ScSortInfo**[nSorts]),
-                        nCount( nInd2 - nInd1 + 1 ), nStart( nInd1 ),
-                        nUsedSorts( nSorts )
-                    {
-                        for ( sal_uInt16 nSort = 0; nSort < nUsedSorts; nSort++ )
-                        {
-                            ScSortInfo** ppInfo = new ScSortInfo* [nCount];
-                            for ( SCSIZE j = 0; j < nCount; j++ )
-                                ppInfo[j] = new ScSortInfo;
-                            pppInfo[nSort] = ppInfo;
-                        }
-                    }
-                ~ScSortInfoArray()
-                    {
-                        for ( sal_uInt16 nSort = 0; nSort < nUsedSorts; nSort++ )
-                        {
-                            ScSortInfo** ppInfo = pppInfo[nSort];
-                            for ( SCSIZE j = 0; j < nCount; j++ )
-                                delete ppInfo[j];
-                            delete [] ppInfo;
-                        }
-                        delete[] pppInfo;
-                    }
+    ScSortInfoArray( sal_uInt16 nSorts, SCCOLROW nInd1, SCCOLROW nInd2 ) :
+        pppInfo( new ScSortInfo**[nSorts]),
+        nCount( nInd2 - nInd1 + 1 ), nStart( nInd1 ),
+        mnLastIndex(nInd2),
+        nUsedSorts(nSorts),
+        mbKeepQuery(false)
+    {
+        for ( sal_uInt16 nSort = 0; nSort < nUsedSorts; nSort++ )
+        {
+            ScSortInfo** ppInfo = new ScSortInfo* [nCount];
+            for ( SCSIZE j = 0; j < nCount; j++ )
+                ppInfo[j] = new ScSortInfo;
+            pppInfo[nSort] = ppInfo;
+        }
+    }
+
+    ~ScSortInfoArray()
+    {
+        for ( sal_uInt16 nSort = 0; nSort < nUsedSorts; nSort++ )
+        {
+            ScSortInfo** ppInfo = pppInfo[nSort];
+            for ( SCSIZE j = 0; j < nCount; j++ )
+                delete ppInfo[j];
+            delete [] ppInfo;
+        }
+        delete[] pppInfo;
+
+        if (mpRows)
+            std::for_each(mpRows->begin(), mpRows->end(), ScDeleteObjectByPtr<Row>());
+    }
+
+    void SetKeepQuery( bool b ) { mbKeepQuery = b; }
+
+    bool IsKeepQuery() const { return mbKeepQuery; }
+
     ScSortInfo* Get( sal_uInt16 nSort, SCCOLROW nInd )
                     { return (pppInfo[nSort])[ nInd - nStart ]; }
-    void        Swap( SCCOLROW nInd1, SCCOLROW nInd2 )
-                    {
-                        SCSIZE n1 = static_cast<SCSIZE>(nInd1 - nStart);
-                        SCSIZE n2 = static_cast<SCSIZE>(nInd2 - nStart);
-                        for ( sal_uInt16 nSort = 0; nSort < nUsedSorts; nSort++ )
-                        {
-                            ScSortInfo** ppInfo = pppInfo[nSort];
-                            ScSortInfo* pTmp = ppInfo[n1];
-                            ppInfo[n1] = ppInfo[n2];
-                            ppInfo[n2] = pTmp;
-                        }
-                    }
+
+    void Swap( SCCOLROW nInd1, SCCOLROW nInd2 )
+    {
+        SCSIZE n1 = static_cast<SCSIZE>(nInd1 - nStart);
+        SCSIZE n2 = static_cast<SCSIZE>(nInd2 - nStart);
+        for ( sal_uInt16 nSort = 0; nSort < nUsedSorts; nSort++ )
+        {
+            ScSortInfo** ppInfo = pppInfo[nSort];
+            ScSortInfo* pTmp = ppInfo[n1];
+            ppInfo[n1] = ppInfo[n2];
+            ppInfo[n2] = pTmp;
+        }
+
+        if (mpRows)
+        {
+            // Swap rows in data table.
+            RowsType& rRows = *mpRows;
+            std::swap(rRows[n1], rRows[n2]);
+        }
+    }
+
     sal_uInt16      GetUsedSorts() const { return nUsedSorts; }
     ScSortInfo**    GetFirstArray() const { return pppInfo[0]; }
     SCCOLROW    GetStart() const { return nStart; }
+    SCCOLROW GetLast() const { return mnLastIndex; }
     SCSIZE      GetCount() const { return nCount; }
+
+    RowsType& InitDataRows( size_t nRowSize, size_t nColSize )
+    {
+        mpRows.reset(new RowsType);
+        mpRows->reserve(nRowSize);
+        for (size_t i = 0; i < nRowSize; ++i)
+            mpRows->push_back(new Row(nColSize));
+
+        return *mpRows;
+    }
+
+    RowsType* GetDataRows()
+    {
+        return mpRows.get();
+    }
 };
 
-ScSortInfoArray* ScTable::CreateSortInfoArray( SCCOLROW nInd1, SCCOLROW nInd2 )
+ScSortInfoArray* ScTable::CreateSortInfoArray( SCCOLROW nInd1, SCCOLROW nInd2, bool bKeepQuery )
 {
     sal_uInt16 nUsedSorts = 1;
     while ( nUsedSorts < aSortParam.GetSortKeyCount() && aSortParam.maKeyState[nUsedSorts].bDoSort )
         nUsedSorts++;
     ScSortInfoArray* pArray = new ScSortInfoArray( nUsedSorts, nInd1, nInd2 );
+    pArray->SetKeepQuery(bKeepQuery);
+
     if ( aSortParam.bByRow )
     {
         for ( sal_uInt16 nSort = 0; nSort < nUsedSorts; nSort++ )
         {
             SCCOL nCol = static_cast<SCCOL>(aSortParam.maKeyState[nSort].nField);
             ScColumn* pCol = &aCol[nCol];
+            sc::ColumnBlockConstPosition aBlockPos;
+            pCol->InitBlockPosition(aBlockPos);
             for ( SCROW nRow = nInd1; nRow <= nInd2; nRow++ )
             {
                 ScSortInfo* pInfo = pArray->Get( nSort, nRow );
-                pInfo->maCell = pCol->GetCellValue(nRow);
+                pInfo->maCell = pCol->GetCellValue(aBlockPos, nRow);
                 pInfo->nOrg = nRow;
             }
         }
+
+        // Fill row-wise data table.
+        ScSortInfoArray::RowsType& rRows = pArray->InitDataRows(
+            nInd2 - nInd1 + 1, aSortParam.nCol2 - aSortParam.nCol1 + 1);
+
+        for (SCCOL nCol = aSortParam.nCol1; nCol <= aSortParam.nCol2; ++nCol)
+        {
+            ScColumn& rCol = aCol[nCol];
+
+            // Skip reordering of cell formats if the whole span is on the same pattern entry.
+            bool bUniformPattern = rCol.GetPatternCount(nInd1, nInd2) < 2u;
+
+            sc::ColumnBlockConstPosition aBlockPos;
+            rCol.InitBlockPosition(aBlockPos);
+            for (SCROW nRow = nInd1; nRow <= nInd2; ++nRow)
+            {
+                ScSortInfoArray::Row& rRow = *rRows[nRow-nInd1];
+                ScSortInfoArray::Cell& rCell = rRow.maCells[nCol-aSortParam.nCol1];
+
+                rCell.maCell = rCol.GetCellValue(aBlockPos, nRow);
+                rCell.mpAttr = rCol.GetCellTextAttr(aBlockPos, nRow);
+                rCell.mpBroadcaster = rCol.GetBroadcaster(aBlockPos, nRow);
+                rCell.mpNote = rCol.GetCellNote(aBlockPos, nRow);
+
+                if (!bUniformPattern && aSortParam.bIncludePattern)
+                    rCell.mpPattern = rCol.GetPattern(nRow);
+            }
+        }
+
+        if (bKeepQuery)
+        {
+            for (SCROW nRow = nInd1; nRow <= nInd2; ++nRow)
+            {
+                ScSortInfoArray::Row& rRow = *rRows[nRow-nInd1];
+                rRow.mbHidden = RowHidden(nRow);
+                rRow.mbFiltered = RowFiltered(nRow);
+            }
+        }
     }
     else
     {
@@ -302,6 +418,71 @@ ScSortInfoArray* ScTable::CreateSortInfoArray( SCCOLROW nInd1, SCCOLROW nInd2 )
     return pArray;
 }
 
+namespace {
+
+struct SortedColumn : boost::noncopyable
+{
+    typedef mdds::flat_segment_tree<SCROW, const ScPatternAttr*> PatRangeType;
+
+    sc::CellStoreType maCells;
+    sc::CellTextAttrStoreType maCellTextAttrs;
+    sc::BroadcasterStoreType maBroadcasters;
+    sc::CellNoteStoreType maCellNotes;
+
+    PatRangeType maPatterns;
+    PatRangeType::const_iterator miPatternPos;
+
+    SortedColumn( size_t nTopEmptyRows ) :
+        maCells(nTopEmptyRows),
+        maCellTextAttrs(nTopEmptyRows),
+        maBroadcasters(nTopEmptyRows),
+        maCellNotes(nTopEmptyRows),
+        maPatterns(0, MAXROWCOUNT, NULL),
+        miPatternPos(maPatterns.begin()) {}
+
+    void setPattern( SCROW nRow, const ScPatternAttr* pPat )
+    {
+        miPatternPos = maPatterns.insert(miPatternPos, nRow, nRow+1, pPat).first;
+    }
+};
+
+struct SortedRowFlags
+{
+    typedef mdds::flat_segment_tree<SCROW,bool> FlagsType;
+
+    FlagsType maRowsHidden;
+    FlagsType maRowsFiltered;
+    FlagsType::const_iterator miPosHidden;
+    FlagsType::const_iterator miPosFiltered;
+
+    SortedRowFlags() :
+        maRowsHidden(0, MAXROWCOUNT, false),
+        maRowsFiltered(0, MAXROWCOUNT, false),
+        miPosHidden(maRowsHidden.begin()),
+        miPosFiltered(maRowsFiltered.begin()) {}
+
+    void setRowHidden( SCROW nRow, bool b )
+    {
+        miPosHidden = maRowsHidden.insert(miPosHidden, nRow, nRow+1, b).first;
+    }
+
+    void setRowFiltered( SCROW nRow, bool b )
+    {
+        miPosFiltered = maRowsFiltered.insert(miPosFiltered, nRow, nRow+1, b).first;
+    }
+};
+
+struct PatternSpan
+{
+    SCROW mnRow1;
+    SCROW mnRow2;
+    const ScPatternAttr* mpPattern;
+
+    PatternSpan( SCROW nRow1, SCROW nRow2, const ScPatternAttr* pPat ) :
+        mnRow1(nRow1), mnRow2(nRow2), mpPattern(pPat) {}
+};
+
+}
 
 bool ScTable::IsSortCollatorGlobal() const
 {
@@ -341,11 +522,17 @@ void ScTable::DestroySortCollator()
 
 void ScTable::SortReorder( ScSortInfoArray* pArray, ScProgress* pProgress )
 {
-    bool bByRow = aSortParam.bByRow;
-    SCSIZE nCount = pArray->GetCount();
+    if (aSortParam.bByRow)
+    {
+        SortReorderByRow(pArray, pProgress);
+        return;
+    }
+
+    size_t nCount = pArray->GetCount();
     SCCOLROW nStart = pArray->GetStart();
     ScSortInfo** ppInfo = pArray->GetFirstArray();
-    ::std::vector<ScSortInfo*> aTable(nCount);
+
+    std::vector<ScSortInfo*> aTable(nCount);
     SCSIZE nPos;
     for ( nPos = 0; nPos < nCount; nPos++ )
         aTable[ppInfo[nPos]->nOrg - nStart] = ppInfo[nPos];
@@ -356,10 +543,7 @@ void ScTable::SortReorder( ScSortInfoArray* pArray, ScProgress* pProgress )
         SCCOLROW nOrg = ppInfo[nPos]->nOrg;
         if ( nDest != nOrg )
         {
-            if ( bByRow )
-                SwapRow( nDest, nOrg );
-            else
-                SwapCol( static_cast<SCCOL>(nDest), static_cast<SCCOL>(nOrg) );
+            SwapCol( static_cast<SCCOL>(nDest), static_cast<SCCOL>(nOrg) );
             // neue Position des weggeswapten eintragen
             ScSortInfo* p = ppInfo[nPos];
             p->nOrg = nDest;
@@ -373,6 +557,195 @@ void ScTable::SortReorder( ScSortInfoArray* pArray, ScProgress* pProgress )
     }
 }
 
+void ScTable::SortReorderByRow( ScSortInfoArray* pArray, ScProgress* pProgress )
+{
+    SCROW nRow1 = pArray->GetStart();
+    SCROW nRow2 = pArray->GetLast();
+    ScSortInfoArray::RowsType* pRows = pArray->GetDataRows();
+    assert(pRows); // In sort-by-row mode we must have data rows already populated.
+
+    // Detach all formula cells within the sorted range first.
+    sc::EndListeningContext aCxt(*pDocument);
+    DetachFormulaCells(aCxt, aSortParam.nCol1, nRow1, aSortParam.nCol2, nRow2);
+
+    // Cells in the data rows only reference values in the document. Make
+    // a copy before updating the document.
+
+    size_t nColCount = aSortParam.nCol2 - aSortParam.nCol1 + 1;
+    boost::ptr_vector<SortedColumn> aSortedCols; // storage for copied cells.
+    SortedRowFlags aRowFlags;
+    aSortedCols.reserve(nColCount);
+    for (size_t i = 0; i < nColCount; ++i)
+    {
+        // In the sorted column container, element positions and row
+        // positions must match, else formula cells may mis-behave during
+        // grouping.
+        aSortedCols.push_back(new SortedColumn(nRow1));
+    }
+
+    for (size_t i = 0; i < pRows->size(); ++i)
+    {
+        ScSortInfoArray::Row* pRow = (*pRows)[i];
+        for (size_t j = 0; j < pRow->maCells.size(); ++j)
+        {
+            ScAddress aCellPos(aSortParam.nCol1 + j, nRow1 + i, nTab);
+
+            ScSortInfoArray::Cell& rCell = pRow->maCells[j];
+
+            sc::CellStoreType& rCellStore = aSortedCols.at(j).maCells;
+            switch (rCell.maCell.meType)
+            {
+                case CELLTYPE_STRING:
+                    assert(rCell.mpAttr);
+                    rCellStore.push_back(*rCell.maCell.mpString);
+                break;
+                case CELLTYPE_VALUE:
+                    assert(rCell.mpAttr);
+                    rCellStore.push_back(rCell.maCell.mfValue);
+                break;
+                case CELLTYPE_EDIT:
+                    assert(rCell.mpAttr);
+                    rCellStore.push_back(rCell.maCell.mpEditText->Clone());
+                break;
+                case CELLTYPE_FORMULA:
+                {
+                    assert(rCell.mpAttr);
+                    size_t n = rCellStore.size();
+                    sc::CellStoreType::iterator itBlk = rCellStore.push_back(rCell.maCell.mpFormula->Clone(aCellPos));
+
+                    // Join the formula cells as we fill the container.
+                    size_t nOffset = n - itBlk->position;
+                    sc::CellStoreType::position_type aPos(itBlk, nOffset);
+                    sc::SharedFormulaUtil::joinFormulaCellAbove(aPos);
+                }
+                break;
+                default:
+                    assert(!rCell.mpAttr);
+                    rCellStore.push_back_empty();
+            }
+
+            sc::CellTextAttrStoreType& rAttrStore = aSortedCols.at(j).maCellTextAttrs;
+            if (rCell.mpAttr)
+                rAttrStore.push_back(*rCell.mpAttr);
+            else
+                rAttrStore.push_back_empty();
+
+            // At this point each broadcaster instance is managed by 2
+            // containers. We will release those in the original storage
+            // below before transferring them to the document.
+            sc::BroadcasterStoreType& rBCStore = aSortedCols.at(j).maBroadcasters;
+            if (rCell.mpBroadcaster)
+                // A const pointer would be implicitly converted to a bool type.
+                rBCStore.push_back(const_cast<SvtBroadcaster*>(rCell.mpBroadcaster));
+            else
+                rBCStore.push_back_empty();
+
+            // The same with cell note instances ...
+            sc::CellNoteStoreType& rNoteStore = aSortedCols.at(j).maCellNotes;
+            if (rCell.mpNote)
+                rNoteStore.push_back(const_cast<ScPostIt*>(rCell.mpNote));
+            else
+                rNoteStore.push_back_empty();
+
+            if (rCell.mpPattern)
+                aSortedCols.at(j).setPattern(aCellPos.Row(), rCell.mpPattern);
+        }
+
+        if (pArray->IsKeepQuery())
+        {
+            // Hidden and filtered flags are first converted to segments.
+            SCROW nRow = nRow1 + i;
+            aRowFlags.setRowHidden(nRow, pRow->mbHidden);
+            aRowFlags.setRowFiltered(nRow, pRow->mbFiltered);
+        }
+
+        if (pProgress)
+            pProgress->SetStateOnPercent(i);
+    }
+
+    for (size_t i = 0, n = aSortedCols.size(); i < n; ++i)
+    {
+        SCCOL nThisCol = i + aSortParam.nCol1;
+
+        {
+            sc::CellStoreType& rDest = aCol[nThisCol].maCells;
+            sc::CellStoreType& rSrc = aSortedCols[i].maCells;
+            rSrc.transfer(nRow1, nRow2, rDest, nRow1);
+        }
+
+        {
+            sc::CellTextAttrStoreType& rDest = aCol[nThisCol].maCellTextAttrs;
+            sc::CellTextAttrStoreType& rSrc = aSortedCols[i].maCellTextAttrs;
+            rSrc.transfer(nRow1, nRow2, rDest, nRow1);
+        }
+
+        {
+            sc::BroadcasterStoreType& rSrc = aSortedCols[i].maBroadcasters;
+            sc::BroadcasterStoreType& rDest = aCol[nThisCol].maBroadcasters;
+
+            // Release current broadcasters first, to prevent them from getting deleted.
+            rDest.release_range(nRow1, nRow2);
+
+            // Transfer sorted broadcaster segment to the document.
+            rSrc.transfer(nRow1, nRow2, rDest, nRow1);
+        }
+
+        {
+            sc::CellNoteStoreType& rSrc = aSortedCols[i].maCellNotes;
+            sc::CellNoteStoreType& rDest = aCol[nThisCol].maCellNotes;
+
+            // Do the same as broadcaster storage transfer (to prevent double deletion).
+            rDest.release_range(nRow1, nRow2);
+            rSrc.transfer(nRow1, nRow2, rDest, nRow1);
+            aCol[nThisCol].UpdateNoteCaptions(nRow1, nRow2);
+        }
+
+        {
+            // Get all row spans where the pattern is not NULL.
+            std::vector<PatternSpan> aSpans =
+                sc::toSpanArrayWithValue<SCROW,const ScPatternAttr*,PatternSpan>(
+                    aSortedCols[i].maPatterns);
+
+            std::vector<PatternSpan>::iterator it = aSpans.begin(), itEnd = aSpans.end();
+            for (; it != itEnd; ++it)
+            {
+                assert(it->mpPattern); // should never be NULL.
+                aCol[nThisCol].SetPatternArea(it->mnRow1, it->mnRow2, *it->mpPattern, true);
+            }
+        }
+
+        aCol[nThisCol].CellStorageModified();
+    }
+
+    if (pArray->IsKeepQuery())
+    {
+        aRowFlags.maRowsHidden.build_tree();
+        aRowFlags.maRowsFiltered.build_tree();
+
+        // Remove all flags in the range first.
+        SetRowHidden(nRow1, nRow2, false);
+        SetRowFiltered(nRow1, nRow2, false);
+
+        std::vector<sc::RowSpan> aSpans =
+            sc::toSpanArray<SCROW,sc::RowSpan>(aRowFlags.maRowsHidden, nRow1);
+
+        std::vector<sc::RowSpan>::const_iterator it = aSpans.begin(), itEnd = aSpans.end();
+        for (; it != itEnd; ++it)
+            SetRowHidden(it->mnRow1, it->mnRow2, true);
+
+        aSpans = sc::toSpanArray<SCROW,sc::RowSpan>(aRowFlags.maRowsFiltered, nRow1);
+
+        it = aSpans.begin(), itEnd = aSpans.end();
+        for (; it != itEnd; ++it)
+            SetRowFiltered(it->mnRow1, it->mnRow2, true);
+    }
+
+    // Attach all formula cells within sorted range, to have them start listening again.
+    sc::StartListeningContext aStartListenCxt(*pDocument);
+    AttachFormulaCells(
+        aStartListenCxt, aSortParam.nCol1, nRow1, aSortParam.nCol2, nRow2);
+}
+
 short ScTable::CompareCell(
     sal_uInt16 nSort,
     ScRefCellValue& rCell1, SCCOL nCell1Col, SCROW nCell1Row,
@@ -561,40 +934,6 @@ void ScTable::SwapCol(SCCOL nCol1, SCCOL nCol2)
     }
 }
 
-void ScTable::SwapRow(SCROW nRow1, SCROW nRow2)
-{
-    SCCOL nColStart = aSortParam.nCol1;
-    SCCOL nColEnd = aSortParam.nCol2;
-    for (SCCOL nCol = nColStart; nCol <= nColEnd; nCol++)
-    {
-        aCol[nCol].SwapRow(nRow1, nRow2);
-        if (aSortParam.bIncludePattern)
-        {
-            const ScPatternAttr* pPat1 = GetPattern(nCol, nRow1);
-            const ScPatternAttr* pPat2 = GetPattern(nCol, nRow2);
-            if (pPat1 != pPat2)
-            {
-                pDocument->GetPool()->Put(*pPat1);
-                SetPattern(nCol, nRow1, *pPat2, true);
-                SetPattern(nCol, nRow2, *pPat1, true);
-                pDocument->GetPool()->Remove(*pPat1);
-            }
-        }
-    }
-    if (bGlobalKeepQuery)
-    {
-        bool bRow1Hidden = RowHidden(nRow1);
-        bool bRow2Hidden = RowHidden(nRow2);
-        SetRowHidden(nRow1, nRow1, bRow2Hidden);
-        SetRowHidden(nRow2, nRow2, bRow1Hidden);
-
-        bool bRow1Filtered = RowFiltered(nRow1);
-        bool bRow2Filtered = RowFiltered(nRow2);
-        SetRowFiltered(nRow1, nRow1, bRow2Filtered);
-        SetRowFiltered(nRow2, nRow2, bRow1Filtered);
-    }
-}
-
 short ScTable::Compare(SCCOLROW nIndex1, SCCOLROW nIndex2) const
 {
     short nRes;
@@ -662,12 +1001,15 @@ void ScTable::Sort(const ScSortParam& rSortParam, bool bKeepQuery, ScProgress* p
         {
             if(pProgress)
                 pProgress->SetState( 0, nLastRow-nRow1 );
-            ScSortInfoArray* pArray = CreateSortInfoArray( nRow1, nLastRow );
+
+            boost::scoped_ptr<ScSortInfoArray> pArray(CreateSortInfoArray(nRow1, nLastRow, bKeepQuery));
+
             if ( nLastRow - nRow1 > 255 )
-                DecoladeRow( pArray, nRow1, nLastRow );
-            QuickSort( pArray, nRow1, nLastRow );
-            SortReorder( pArray, pProgress );
-            delete pArray;
+                DecoladeRow(pArray.get(), nRow1, nLastRow);
+
+            QuickSort(pArray.get(), nRow1, nLastRow);
+            SortReorder(pArray.get(), pProgress);
+
             // #i59745# update position of caption objects of cell notes --> reported at (SortReorder) ScColumn::SwapCellNotes level
         }
     }
@@ -684,10 +1026,12 @@ void ScTable::Sort(const ScSortParam& rSortParam, bool bKeepQuery, ScProgress* p
         {
             if(pProgress)
                 pProgress->SetState( 0, nLastCol-nCol1 );
-            ScSortInfoArray* pArray = CreateSortInfoArray( nCol1, nLastCol );
-            QuickSort( pArray, nCol1, nLastCol );
-            SortReorder( pArray, pProgress );
-            delete pArray;
+
+            boost::scoped_ptr<ScSortInfoArray> pArray(CreateSortInfoArray(nCol1, nLastCol, bKeepQuery));
+
+            QuickSort(pArray.get(), nCol1, nLastCol);
+            SortReorder(pArray.get(), pProgress);
+
             // #i59745# update position of caption objects of cell notes --> reported at (SortReorder) ScColumn::SwapCellNotes level
         }
     }
@@ -1684,9 +2028,9 @@ void ScTable::TopTenQuery( ScQueryParam& rParam )
                     bSortCollatorInitialized = true;
                     InitSortCollator( aLocalSortParam );
                 }
-                ScSortInfoArray* pArray = CreateSortInfoArray( nRow1, rParam.nRow2 );
-                DecoladeRow( pArray, nRow1, rParam.nRow2 );
-                QuickSort( pArray, nRow1, rParam.nRow2 );
+                boost::scoped_ptr<ScSortInfoArray> pArray(CreateSortInfoArray(nRow1, rParam.nRow2, bGlobalKeepQuery));
+                DecoladeRow( pArray.get(), nRow1, rParam.nRow2 );
+                QuickSort( pArray.get(), nRow1, rParam.nRow2 );
                 ScSortInfo** ppInfo = pArray->GetFirstArray();
                 SCSIZE nValidCount = nCount;
                 // keine Note-/Leerzellen zaehlen, sind ans Ende sortiert
@@ -1763,7 +2107,6 @@ void ScTable::TopTenQuery( ScQueryParam& rParam )
                     rItem.meType = ScQueryEntry::ByValue;
                     rItem.mfVal = 0;
                 }
-                delete pArray;
             }
             break;
             default:
diff --git a/sc/source/core/data/table7.cxx b/sc/source/core/data/table7.cxx
index e8e82d4d64f1..b5ebc125946d 100644
--- a/sc/source/core/data/table7.cxx
+++ b/sc/source/core/data/table7.cxx
@@ -12,6 +12,7 @@
 #include <document.hxx>
 #include <clipparam.hxx>
 #include <bcaslot.hxx>
+#include <segmenttree.hxx>
 
 void ScTable::DeleteBeforeCopyFromClip( sc::CopyFromClipContext& rCxt, const ScTable& rClipTab )
 {
@@ -54,4 +55,26 @@ void ScTable::PostprocessRangeNameUpdate( sc::CompileFormulaContext& rCompileCxt
         aCol[i].PostprocessRangeNameUpdate(rCompileCxt);
 }
 
+void ScTable::UpdateScriptTypes( SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2 )
+{
+    if (!ValidCol(nCol1) || !ValidCol(nCol2) || nCol1 > nCol2)
+        return;
+
+    for (SCCOL nCol = nCol1; nCol <= nCol2; ++nCol)
+        aCol[nCol].UpdateScriptTypes(nRow1, nRow2);
+}
+
+bool ScTable::HasUniformRowHeight( SCROW nRow1, SCROW nRow2 ) const
+{
+    if (!ValidRow(nRow1) || !ValidRow(nRow2) || nRow1 > nRow2)
+        return false;
+
+    ScFlatUInt16RowSegments::RangeData aData;
+    if (!mpRowHeights->getRangeData(nRow1, aData))
+        // Search failed.
+        return false;
+
+    return nRow2 <= aData.mnRow2;
+}
+
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/source/ui/docshell/dbdocfun.cxx b/sc/source/ui/docshell/dbdocfun.cxx
index 13f42cabf304..1e7cbdbbd703 100644
--- a/sc/source/ui/docshell/dbdocfun.cxx
+++ b/sc/source/ui/docshell/dbdocfun.cxx
@@ -493,7 +493,21 @@ sal_Bool ScDBDocFunc::Sort( SCTAB nTab, const ScSortParam& rSortParam,
 
     WaitObject aWait( rDocShell.GetActiveDialogParent() );
 
-    sal_Bool bRepeatQuery = false;                          // bestehenden Filter wiederholen?
+    SCROW nStartRow = aLocalParam.nRow1 + (aLocalParam.bHasHeader ? 1 : 0);
+
+    // Calculate the script types for all cells in the sort range beforehand.
+    // This will speed up the row height adjustment that takes place after the
+    // sort.
+    pDoc->UpdateScriptTypes(
+        ScAddress(aLocalParam.nCol1,nStartRow,nTab),
+        aLocalParam.nCol2-aLocalParam.nCol1+1,
+        aLocalParam.nRow2-nStartRow+1);
+
+    // No point adjusting row heights after the sort when all rows have the same height.
+    bool bUniformRowHeight =
+        pDoc->HasUniformRowHeight(nTab, nStartRow, aLocalParam.nRow2);
+
+    bool bRepeatQuery = false;                          // bestehenden Filter wiederholen?
     ScQueryParam aQueryParam;
     pDBData->GetQueryParam( aQueryParam );
     if ( aQueryParam.GetEntry(0).bDoQuery )
@@ -627,8 +641,9 @@ sal_Bool ScDBDocFunc::Sort( SCTAB nTab, const ScSortParam& rSortParam,
         }
     }
 
-    ScRange aDirtyRange( aLocalParam.nCol1, aLocalParam.nRow1, nTab,
-        aLocalParam.nCol2, aLocalParam.nRow2, nTab );
+    ScRange aDirtyRange(
+        aLocalParam.nCol1, nStartRow, nTab,
+        aLocalParam.nCol2, aLocalParam.nRow2, nTab);
     pDoc->SetDirty( aDirtyRange );
 
     if (bPaint)
@@ -654,8 +669,8 @@ sal_Bool ScDBDocFunc::Sort( SCTAB nTab, const ScSortParam& rSortParam,
         rDocShell.PostPaint(ScRange(nStartX, nStartY, nTab, nEndX, nEndY, nTab), nPaint);
     }
 
-    //  AdjustRowHeight( aLocalParam.nRow1, aLocalParam.nRow2, bPaint );
-    rDocShell.AdjustRowHeight( aLocalParam.nRow1, aLocalParam.nRow2, nTab );
+    if (!bUniformRowHeight)
+        rDocShell.AdjustRowHeight(nStartRow, aLocalParam.nRow2, nTab);
 
     // #i59745# set collected drawing undo actions at sorting undo action
     if( pUndoAction && pDrawLayer )