tdf#126573 Add Excel2021 array function SORT to Calc

TODO/WIP: oasis proposal
More information about how this new function works:
https://support.microsoft.com/en-au/office/sort-function-22f63bd0-ccc8-492f-953d-c20e8e44b86c
https://exceljet.net/functions/sort-function

Note: Move ScSortInfoArray class to sortparam.hxx, which is a more
logical place.

Change-Id: I70e720e93ba0414d54cb3437de0bfa066508fe30
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/164778
Tested-by: Jenkins
Reviewed-by: Balazs Varga <balazs.varga.extern@allotropia.de>

11 files changed, 602 insertions, 179 deletions

diff --git a/sc/source/core/data/funcdesc.cxx b/sc/source/core/data/funcdesc.cxx
index 1137d13ce14f..677f76453ff5 100644
--- a/sc/source/core/data/funcdesc.cxx
+++ b/sc/source/core/data/funcdesc.cxx
@@ -788,6 +788,7 @@ ScFunctionList::ScFunctionList( bool bEnglishFunctionNames )
         { SC_OPCODE_FOURIER, ENTRY(SC_OPCODE_FOURIER_ARY), 0, ID_FUNCTION_GRP_MATRIX, HID_FUNC_FOURIER, 5, { 0, 0, 1, 1, 1 }, 0 },
         { SC_OPCODE_RANDBETWEEN_NV, ENTRY(SC_OPCODE_RANDBETWEEN_NV_ARY), 0, ID_FUNCTION_GRP_MATH, HID_FUNC_RANDBETWEEN_NV, 2, { 0, 0 }, 0 },
         { SC_OPCODE_FILTER, ENTRY(SC_OPCODE_FILTER_ARY), 0, ID_FUNCTION_GRP_TABLE, HID_FUNC_FILTER_MS, 3, { 0, 0, 1 }, 0 },
+        { SC_OPCODE_SORT, ENTRY(SC_OPCODE_SORT_ARY), 0, ID_FUNCTION_GRP_TABLE, HID_FUNC_SORT_MS, 4, { 0, 1, 1, 1 }, 0 },
     };
 
     ScFuncDesc* pDesc = nullptr;
diff --git a/sc/source/core/data/sortparam.cxx b/sc/source/core/data/sortparam.cxx
index 3e1506dbad7c..37e44794a4df 100644
--- a/sc/source/core/data/sortparam.cxx
+++ b/sc/source/core/data/sortparam.cxx
@@ -34,6 +34,7 @@ ScSortParam::ScSortParam()
 
 ScSortParam::ScSortParam( const ScSortParam& r ) :
         nCol1(r.nCol1),nRow1(r.nRow1),nCol2(r.nCol2),nRow2(r.nRow2),
+        nSourceTab(r.nSourceTab),
         aDataAreaExtras(r.aDataAreaExtras),
         nUserIndex(r.nUserIndex),
         bHasHeader(r.bHasHeader),bByRow(r.bByRow),bCaseSens(r.bCaseSens),
@@ -55,6 +56,7 @@ void ScSortParam::Clear()
 
     nCol1=nCol2=nDestCol = 0;
     nRow1=nRow2=nDestRow = 0;
+    nSourceTab = 0;
     aDataAreaExtras = ScDataAreaExtras();
     aDataAreaExtras.mbCellDrawObjects = true;
     aDataAreaExtras.mbCellFormats = true;
@@ -81,6 +83,7 @@ ScSortParam& ScSortParam::operator=( const ScSortParam& r )
     nRow1           = r.nRow1;
     nCol2           = r.nCol2;
     nRow2           = r.nRow2;
+    nSourceTab      = r.nSourceTab;
     aDataAreaExtras = r.aDataAreaExtras;
     nUserIndex      = r.nUserIndex;
     bHasHeader      = r.bHasHeader;
@@ -125,6 +128,7 @@ bool ScSortParam::operator==( const ScSortParam& rOther ) const
         && (nRow1           == rOther.nRow1)
         && (nCol2           == rOther.nCol2)
         && (nRow2           == rOther.nRow2)
+        && (nSourceTab      == rOther.nSourceTab)
         && (aDataAreaExtras == rOther.aDataAreaExtras)
         && (bHasHeader      == rOther.bHasHeader)
         && (bByRow          == rOther.bByRow)
@@ -156,6 +160,7 @@ bool ScSortParam::operator==( const ScSortParam& rOther ) const
 
 ScSortParam::ScSortParam( const ScSubTotalParam& rSub, const ScSortParam& rOld ) :
         nCol1(rSub.nCol1),nRow1(rSub.nRow1),nCol2(rSub.nCol2),nRow2(rSub.nRow2),
+        nSourceTab(0),
         aDataAreaExtras(rOld.aDataAreaExtras),
         nUserIndex(rSub.nUserIndex),
         bHasHeader(true),bByRow(true),bCaseSens(rSub.bCaseSens),bNaturalSort(rOld.bNaturalSort),
@@ -205,7 +210,9 @@ ScSortParam::ScSortParam( const ScSubTotalParam& rSub, const ScSortParam& rOld )
 }
 
 ScSortParam::ScSortParam( const ScQueryParam& rParam, SCCOL nCol ) :
-        nCol1(nCol),nRow1(rParam.nRow1),nCol2(nCol),nRow2(rParam.nRow2),nUserIndex(0),
+        nCol1(nCol),nRow1(rParam.nRow1),nCol2(nCol),nRow2(rParam.nRow2),
+        nSourceTab(rParam.nTab),
+        nUserIndex(0),
         bHasHeader(rParam.bHasHeader),bByRow(true),bCaseSens(rParam.bCaseSens),
         bNaturalSort(false),
 //TODO: what about Locale and Algorithm?
diff --git a/sc/source/core/data/table3.cxx b/sc/source/core/data/table3.cxx
index 47fc047909e9..084d4a8dc868 100644
--- a/sc/source/core/data/table3.cxx
+++ b/sc/source/core/data/table3.cxx
@@ -48,7 +48,6 @@
 #include <queryentry.hxx>
 #include <subtotalparam.hxx>
 #include <docpool.hxx>
-#include <cellvalue.hxx>
 #include <tokenarray.hxx>
 #include <mtvcellfunc.hxx>
 #include <columnspanset.hxx>
@@ -218,180 +217,6 @@ static short Compare( const OUString &sInput1, const OUString &sInput2,
 
 }
 
-namespace {
-
-struct ScSortInfo final
-{
-    ScRefCellValue maCell;
-    SCCOLROW        nOrg;
-};
-
-}
-
-class ScSortInfoArray
-{
-public:
-
-    struct Cell
-    {
-        ScRefCellValue maCell;
-        const sc::CellTextAttr* mpAttr;
-        const ScPostIt* mpNote;
-        std::vector<SdrObject*> maDrawObjects;
-        CellAttributeHolder maPattern;
-
-        Cell() : mpAttr(nullptr), mpNote(nullptr),  maPattern() {}
-    };
-
-    struct Row
-    {
-        std::vector<Cell> maCells;
-
-        bool mbHidden:1;
-        bool mbFiltered:1;
-
-        explicit Row( size_t nColSize ) : maCells(nColSize, Cell()), mbHidden(false), mbFiltered(false) {}
-    };
-
-    typedef std::vector<Row> RowsType;
-
-private:
-    std::unique_ptr<RowsType> mpRows; /// row-wise data table for sort by row operation.
-
-    std::vector<std::unique_ptr<ScSortInfo[]>> mvppInfo;
-    SCCOLROW        nStart;
-    SCCOLROW        mnLastIndex; /// index of last non-empty cell position.
-
-    std::vector<SCCOLROW> maOrderIndices;
-    bool mbKeepQuery;
-    bool mbUpdateRefs;
-
-public:
-    ScSortInfoArray(const ScSortInfoArray&) = delete;
-    const ScSortInfoArray& operator=(const ScSortInfoArray&) = delete;
-
-    ScSortInfoArray( sal_uInt16 nSorts, SCCOLROW nInd1, SCCOLROW nInd2 ) :
-        mvppInfo(nSorts),
-        nStart( nInd1 ),
-        mnLastIndex(nInd2),
-        mbKeepQuery(false),
-        mbUpdateRefs(false)
-    {
-        SCSIZE nCount( nInd2 - nInd1 + 1 );
-        if (nSorts)
-        {
-            for ( sal_uInt16 nSort = 0; nSort < nSorts; nSort++ )
-            {
-                mvppInfo[nSort].reset(new ScSortInfo[nCount]);
-            }
-        }
-
-        for (size_t i = 0; i < nCount; ++i)
-            maOrderIndices.push_back(i+nStart);
-    }
-
-    void SetKeepQuery( bool b ) { mbKeepQuery = b; }
-
-    bool IsKeepQuery() const { return mbKeepQuery; }
-
-    void SetUpdateRefs( bool b ) { mbUpdateRefs = b; }
-
-    bool IsUpdateRefs() const { return mbUpdateRefs; }
-
-    /**
-     * Call this only during normal sorting, not from reordering.
-     */
-    std::unique_ptr<ScSortInfo[]> const & GetFirstArray() const
-    {
-        return mvppInfo[0];
-    }
-
-    /**
-     * Call this only during normal sorting, not from reordering.
-     */
-    ScSortInfo & Get( sal_uInt16 nSort, SCCOLROW nInd )
-    {
-        return mvppInfo[nSort][ nInd - nStart ];
-    }
-
-    /**
-     * Call this only during normal sorting, not from reordering.
-     */
-    void Swap( SCCOLROW nInd1, SCCOLROW nInd2 )
-    {
-        if (nInd1 == nInd2) // avoid self-move-assign
-            return;
-        SCSIZE n1 = static_cast<SCSIZE>(nInd1 - nStart);
-        SCSIZE n2 = static_cast<SCSIZE>(nInd2 - nStart);
-        for ( sal_uInt16 nSort = 0; nSort < static_cast<sal_uInt16>(mvppInfo.size()); nSort++ )
-        {
-            auto & ppInfo = mvppInfo[nSort];
-            std::swap(ppInfo[n1], ppInfo[n2]);
-        }
-
-        std::swap(maOrderIndices[n1], maOrderIndices[n2]);
-
-        if (mpRows)
-        {
-            // Swap rows in data table.
-            RowsType& rRows = *mpRows;
-            std::swap(rRows[n1], rRows[n2]);
-        }
-    }
-
-    void SetOrderIndices( std::vector<SCCOLROW>&& rIndices )
-    {
-        maOrderIndices = std::move(rIndices);
-    }
-
-    /**
-     * @param rIndices indices are actual row positions on the sheet, not an
-     *                 offset from the top row.
-     */
-    void ReorderByRow( const std::vector<SCCOLROW>& rIndices )
-    {
-        if (!mpRows)
-            return;
-
-        RowsType& rRows = *mpRows;
-
-        std::vector<SCCOLROW> aOrderIndices2;
-        aOrderIndices2.reserve(rIndices.size());
-
-        RowsType aRows2;
-        aRows2.reserve(rRows.size());
-
-        for (const auto& rIndex : rIndices)
-        {
-            size_t nPos = rIndex - nStart; // switch to an offset to top row.
-            aRows2.push_back(rRows[nPos]);
-            aOrderIndices2.push_back(maOrderIndices[nPos]);
-        }
-
-        rRows.swap(aRows2);
-        maOrderIndices.swap(aOrderIndices2);
-    }
-
-    sal_uInt16      GetUsedSorts() const { return mvppInfo.size(); }
-
-    SCCOLROW    GetStart() const { return nStart; }
-    SCCOLROW GetLast() const { return mnLastIndex; }
-
-    const std::vector<SCCOLROW>& GetOrderIndices() const { return maOrderIndices; }
-
-    RowsType& InitDataRows( size_t nRowSize, size_t nColSize )
-    {
-        mpRows.reset(new RowsType);
-        mpRows->resize(nRowSize, Row(nColSize));
-        return *mpRows;
-    }
-
-    RowsType* GetDataRows()
-    {
-        return mpRows.get();
-    }
-};
-
 // Assume that we can handle 512MB, which with a ~100 bytes
 // ScSortInfoArray::Cell element for 500MB are about 5 million cells plus
 // overhead in one chunk.
diff --git a/sc/source/core/inc/interpre.hxx b/sc/source/core/inc/interpre.hxx
index 960390f2b206..b984f8a4e37c 100644
--- a/sc/source/core/inc/interpre.hxx
+++ b/sc/source/core/inc/interpre.hxx
@@ -31,6 +31,7 @@
 #include <math.hxx>
 #include <kahan.hxx>
 #include <queryentry.hxx>
+#include <sortparam.hxx>
 #include "parclass.hxx"
 
 #include <map>
@@ -268,6 +269,9 @@ private:
 
     VolatileType meVolatileType;
 
+    // sort parameters
+    ScSortParam aSortParam;
+
     void MakeMatNew(ScMatrixRef& rMat, SCSIZE nC, SCSIZE nR);
 
     /// Merge global and document specific settings.
@@ -557,6 +561,22 @@ private:
     // Returns true if last jump was executed and result matrix pushed.
     bool JumpMatrix( short nStackLevel );
 
+    // Advance sort
+    static void DecoladeRow(ScSortInfoArray* pArray, SCROW nRow1, SCROW nRow2);
+
+    std::unique_ptr<ScSortInfoArray> CreateFastSortInfoArray(
+        const ScSortParam& rSortParam, bool bMatrix, SCCOLROW nInd1, SCCOLROW nInd2);
+    std::vector<SCCOLROW> GetSortOrder(const ScSortParam& rSortParam, const ScMatrixRef& pMatSrc);
+
+    void QuickSort(ScSortInfoArray* pArray, const ScMatrixRef& pMatSrc, SCCOLROW nLo, SCCOLROW nHi);
+
+    short Compare(ScSortInfoArray* pArray, const ScMatrixRef& pMatSrc, SCCOLROW nIndex1, SCCOLROW nIndex2) const;
+    short CompareCell( sal_uInt16 nSort,
+        ScRefCellValue& rCell1, ScRefCellValue& rCell2 ) const;
+    short CompareMatrixCell( const ScMatrixRef& pMatSrc, sal_uInt16 nSort, SCCOL nCell1Col, SCROW nCell1Row,
+        SCCOL nCell2Col, SCROW nCell2Row ) const;
+    // Advance sort end
+
     double Compare( ScQueryOp eOp );
     /** @param pOptions
             NULL means case sensitivity document option is to be used!
@@ -691,6 +711,7 @@ private:
     void ScVLookup();
     void ScXLookup();
     void ScFilter();
+    void ScSort();
     void ScSubTotal();
 
     // If upon call rMissingField==true then the database field parameter may be
diff --git a/sc/source/core/tool/interpr1.cxx b/sc/source/core/tool/interpr1.cxx
index 34aaba80de96..c1a4af803ef1 100644
--- a/sc/source/core/tool/interpr1.cxx
+++ b/sc/source/core/tool/interpr1.cxx
@@ -61,7 +61,6 @@
 #include <externalrefmgr.hxx>
 #include <doubleref.hxx>
 #include <queryparam.hxx>
-#include <queryentry.hxx>
 #include <queryiter.hxx>
 #include <tokenarray.hxx>
 #include <compare.hxx>
@@ -8303,6 +8302,208 @@ void ScInterpreter::ScFilter()
         PushError(FormulaError::NestedArray);
 }
 
+void ScInterpreter::ScSort()
+{
+    sal_uInt8 nParamCount = GetByte();
+    if (!MustHaveParamCount(nParamCount, 1, 4))
+        return;
+
+    // Create sort data
+    ScSortParam aSortData;
+
+    // 4th argument optional
+    aSortData.bByRow = true; // default: By_Col = false --> bByRow = true
+    if (nParamCount == 4)
+        aSortData.bByRow = !GetBool();
+
+    // 3rd argument optional
+    std::vector<double> aSortOrderValues{ 1.0 }; // default: 1 = asc, -1 = desc
+    if (nParamCount >= 3)
+    {
+        bool bMissing = IsMissing();
+        ScMatrixRef pSortOrder = GetMatrix();
+        if (!bMissing)
+        {
+            aSortOrderValues.clear();
+            pSortOrder->GetDoubleArray(aSortOrderValues);
+            for (const double& sortOrder : aSortOrderValues)
+            {
+                if (sortOrder != 1.0 && sortOrder != -1.0)
+                {
+                    PushIllegalParameter();
+                    return;
+                }
+            }
+        }
+    }
+
+    // 2nd argument optional
+    std::vector<double> aSortIndexValues{ 0.0 }; // default: first column or row
+    if (nParamCount >= 2)
+    {
+        bool bMissing = IsMissing();
+        ScMatrixRef pSortIndex = GetMatrix();
+        if (!bMissing)
+        {
+            aSortIndexValues.clear();
+            pSortIndex->GetDoubleArray(aSortIndexValues);
+            for (double& sortIndex : aSortIndexValues)
+            {
+                if (sortIndex < 1)
+                {
+                    PushIllegalParameter();
+                    return;
+                }
+                else
+                    sortIndex--;
+            }
+        }
+    }
+
+    if (aSortIndexValues.size() != aSortOrderValues.size() && aSortOrderValues.size() > 1)
+    {
+        PushIllegalParameter();
+        return;
+    }
+
+    // 1st argument is vector to be sorted
+    SCSIZE nsC = 0, nsR = 0;
+    ScMatrixRef pMatSrc = nullptr;
+    switch ( GetStackType() )
+    {
+        case svSingleRef:
+            PopSingleRef(aSortData.nCol1, aSortData.nRow1, aSortData.nSourceTab);
+            aSortData.nCol2   = aSortData.nCol1;
+            aSortData.nRow2   = aSortData.nRow1;
+            nsC = aSortData.nCol2 - aSortData.nCol1 + 1;
+            nsR = aSortData.nRow2 - aSortData.nRow1 + 1;
+        break;
+        case svDoubleRef:
+        {
+            SCTAB nTab2 = 0;
+            PopDoubleRef(aSortData.nCol1, aSortData.nRow1, aSortData.nSourceTab, aSortData.nCol2, aSortData.nRow2, nTab2);
+            if (aSortData.nSourceTab != nTab2)
+            {
+                PushIllegalParameter();
+                return;
+            }
+            nsC = aSortData.nCol2 - aSortData.nCol1 + 1;
+            nsR = aSortData.nRow2 - aSortData.nRow1 + 1;
+        }
+        break;
+        case svMatrix:
+        case svExternalSingleRef:
+        case svExternalDoubleRef:
+        {
+            pMatSrc = GetMatrix();
+            if (!pMatSrc)
+            {
+                PushIllegalParameter();
+                return;
+            }
+            pMatSrc->GetDimensions(nsC, nsR);
+            aSortData.nCol2 = nsC - 1; // aSortData.nCol1 = 0
+            aSortData.nRow2 = nsR - 1; // aSortData.nRow1 = 0
+        }
+        break;
+
+        default:
+            PushIllegalParameter();
+            return;
+    }
+
+    aSortData.maKeyState.resize(aSortIndexValues.size());
+    for (size_t i = 0; i < aSortIndexValues.size(); i++)
+    {
+        SCSIZE fIndex = static_cast<SCSIZE>(double_to_int32(aSortIndexValues[i]));
+        if ((aSortData.bByRow && fIndex + 1 > nsC) || (!aSortData.bByRow && fIndex + 1 > nsR))
+        {
+            PushIllegalParameter();
+            return;
+        }
+
+        aSortData.maKeyState[i].bDoSort = true;
+        aSortData.maKeyState[i].nField = (aSortData.bByRow ? aSortData.nCol1 : aSortData.nRow1) + fIndex;
+
+        if (aSortIndexValues.size() == aSortOrderValues.size())
+            aSortData.maKeyState[i].bAscending = (aSortOrderValues[i] == 1.0);
+        else
+            aSortData.maKeyState[i].bAscending = (aSortOrderValues[0] == 1.0);
+    }
+
+    // sorting...
+    std::vector<SCCOLROW> aOrderIndices = GetSortOrder(aSortData, pMatSrc);
+
+    SCCOLROW nStartPos = (!aSortData.bByRow ? aSortData.nCol1 : aSortData.nRow1);
+    size_t nCount = aOrderIndices.size();
+    std::vector<SCCOLROW> aPosTable(nCount);
+
+    for (size_t i = 0; i < nCount; ++i)
+        aPosTable[aOrderIndices[i] - nStartPos] = i;
+
+    ScMatrixRef pResMat = nullptr;
+    if (!aOrderIndices.empty())
+    {
+        pResMat = GetNewMat(nsC, nsR, /*bEmpty*/true);
+        if (!pMatSrc)
+        {
+            ScCellIterator aCellIter(mrDoc, ScRange(aSortData.nCol1, aSortData.nRow1, aSortData.nSourceTab,
+                aSortData.nCol2, aSortData.nRow2, aSortData.nSourceTab));
+            for (bool bHas = aCellIter.first(); bHas; bHas = aCellIter.next())
+            {
+                SCSIZE nThisCol = static_cast<SCSIZE>(aCellIter.GetPos().Col() - aSortData.nCol1);
+                SCSIZE nThisRow = static_cast<SCSIZE>(aCellIter.GetPos().Row() - aSortData.nRow1);
+
+                ScRefCellValue aCell = aCellIter.getRefCellValue();
+                if (aCell.hasNumeric())
+                {
+                    if (aSortData.bByRow)
+                        pResMat->PutDouble(GetCellValue(aCellIter.GetPos(), aCell), nThisCol, aPosTable[nThisRow]);
+                    else
+                        pResMat->PutDouble(GetCellValue(aCellIter.GetPos(), aCell), aPosTable[nThisCol], nThisRow);
+                }
+                else
+                {
+                    svl::SharedString aStr;
+                    GetCellString(aStr, aCell);
+                    if (aSortData.bByRow)
+                        pResMat->PutString(aStr, nThisCol, aPosTable[nThisRow]);
+                    else
+                        pResMat->PutString(aStr, aPosTable[nThisCol], nThisRow);
+                }
+            }
+        }
+        else
+        {
+            for (SCCOL ci = aSortData.nCol1; ci <= aSortData.nCol2; ci++)
+            {
+                for (SCROW rj = aSortData.nRow1; rj <= aSortData.nRow2; rj++)
+                {
+                    if (pMatSrc->IsStringOrEmpty(ci, rj))
+                    {
+                        if (aSortData.bByRow)
+                            pResMat->PutString(pMatSrc->GetString(ci, rj), ci, aPosTable[rj]);
+                        else
+                            pResMat->PutString(pMatSrc->GetString(ci, rj), aPosTable[ci], rj);
+                    }
+                    else
+                    {
+                        if (aSortData.bByRow)
+                            pResMat->PutDouble(pMatSrc->GetDouble(ci, rj), ci, aPosTable[rj]);
+                        else
+                            pResMat->PutDouble(pMatSrc->GetDouble(ci, rj), aPosTable[ci], rj);
+                    }
+                }
+            }
+        }
+    }
+
+    if (pResMat)
+        PushMatrix(pResMat);
+    else
+        PushError(FormulaError::NestedArray);
+}
+
 void ScInterpreter::ScSubTotal()
 {
     sal_uInt8 nParamCount = GetByte();
diff --git a/sc/source/core/tool/interpr3.cxx b/sc/source/core/tool/interpr3.cxx
index 88b32b44af1e..17e52858637b 100644
--- a/sc/source/core/tool/interpr3.cxx
+++ b/sc/source/core/tool/interpr3.cxx
@@ -26,6 +26,8 @@
 #include <dociter.hxx>
 #include <matrixoperators.hxx>
 #include <scmatrix.hxx>
+#include <columniterator.hxx>
+#include <unotools/collatorwrapper.hxx>
 
 #include <cassert>
 #include <cmath>
@@ -4140,6 +4142,367 @@ void ScInterpreter::GetNumberSequenceArray( sal_uInt8 nParamCount, vector<double
         PopError();
 }
 
+void ScInterpreter::DecoladeRow( ScSortInfoArray* pArray, SCROW nRow1, SCROW nRow2 )
+{
+    SCROW nRow;
+    int nMax = nRow2 - nRow1;
+    for (SCROW i = nRow1; (i + 4) <= nRow2; i += 4)
+    {
+        nRow = comphelper::rng::uniform_int_distribution(0, nMax - 1);
+        pArray->Swap(i, nRow1 + nRow);
+    }
+}
+
+std::unique_ptr<ScSortInfoArray> ScInterpreter::CreateFastSortInfoArray(
+    const ScSortParam& rSortParam, bool bMatrix, SCCOLROW nInd1, SCCOLROW nInd2 )
+{
+    sal_uInt16 nUsedSorts = 1;
+    while (nUsedSorts < rSortParam.GetSortKeyCount() && rSortParam.maKeyState[nUsedSorts].bDoSort)
+        nUsedSorts++;
+    std::unique_ptr<ScSortInfoArray> pArray(new ScSortInfoArray(nUsedSorts, nInd1, nInd2));
+
+    if (rSortParam.bByRow)
+    {
+        for (sal_uInt16 nSort = 0; nSort < nUsedSorts; nSort++)
+        {
+            if (!bMatrix)
+            {
+                SCCOL nCol = static_cast<SCCOL>(rSortParam.maKeyState[nSort].nField);
+                std::optional<sc::ColumnIterator> pIter = mrDoc.GetColumnIterator(rSortParam.nSourceTab, nCol, nInd1, nInd2);
+                assert(pIter->hasCell());
+
+                for (SCROW nRow = nInd1; nRow <= nInd2; nRow++, pIter->next())
+                {
+                    ScSortInfo& rInfo = pArray->Get(nSort, nRow);
+                    rInfo.maCell = pIter->getCell();
+                    rInfo.nOrg = nRow;
+                }
+            }
+            else
+            {
+                for (SCROW nRow = nInd1; nRow <= nInd2; nRow++)
+                {
+                    ScSortInfo& rInfo = pArray->Get(nSort, nRow);
+                    rInfo.nOrg = nRow;
+                }
+            }
+        }
+    }
+    else
+    {
+        for (sal_uInt16 nSort = 0; nSort < nUsedSorts; nSort++)
+        {
+            if (!bMatrix)
+            {
+                SCROW nRow = rSortParam.maKeyState[nSort].nField;
+                for (SCCOL nCol = static_cast<SCCOL>(nInd1);
+                    nCol <= static_cast<SCCOL>(nInd2); nCol++)
+                {
+                    ScSortInfo& rInfo = pArray->Get(nSort, nCol);
+                    rInfo.maCell = mrDoc.GetRefCellValue(ScAddress(nCol, nRow, rSortParam.nSourceTab));
+                    rInfo.nOrg = nCol;
+                }
+            }
+            else
+            {
+                for (SCCOL nCol = static_cast<SCCOL>(nInd1);
+                    nCol <= static_cast<SCCOL>(nInd2); nCol++)
+                {
+                    ScSortInfo& rInfo = pArray->Get(nSort, nCol);
+                    rInfo.nOrg = nCol;
+                }
+            }
+        }
+    }
+    return pArray;
+}
+
+std::vector<SCCOLROW> ScInterpreter::GetSortOrder( const ScSortParam& rSortParam, const ScMatrixRef& pMatSrc )
+{
+    std::vector<SCCOLROW> aOrderIndices;
+    aSortParam = rSortParam;
+    if (rSortParam.bByRow)
+    {
+        const SCROW nLastRow = rSortParam.nRow2;
+        const SCROW nRow1 = (rSortParam.bHasHeader ? rSortParam.nRow1 + 1 : rSortParam.nRow1);
+        if (nRow1 < nLastRow)
+        {
+            std::unique_ptr<ScSortInfoArray> pArray(CreateFastSortInfoArray(
+                aSortParam, (pMatSrc != nullptr), nRow1, nLastRow));
+
+            if (nLastRow - nRow1 > 255)
+                DecoladeRow(pArray.get(), nRow1, nLastRow);
+
+            QuickSort(pArray.get(), pMatSrc, nRow1, nLastRow);
+            aOrderIndices = pArray->GetOrderIndices();
+        }
+    }
+    else
+    {
+        const SCCOL nLastCol = rSortParam.nCol2;
+        const SCCOL nCol1 = (rSortParam.bHasHeader ? rSortParam.nCol1 + 1 : rSortParam.nCol1);
+        if (nCol1 < nLastCol)
+        {
+            std::unique_ptr<ScSortInfoArray> pArray(CreateFastSortInfoArray(
+                aSortParam, (pMatSrc != nullptr), nCol1, nLastCol));
+
+            QuickSort(pArray.get(), pMatSrc, nCol1, nLastCol);
+            aOrderIndices = pArray->GetOrderIndices();
+        }
+    }
+    return aOrderIndices;
+}
+
+void ScInterpreter::QuickSort( ScSortInfoArray* pArray, const ScMatrixRef& pMatSrc, SCCOLROW nLo, SCCOLROW nHi )
+{
+    if ((nHi - nLo) == 1)
+    {
+        if (Compare(pArray, pMatSrc, nLo, nHi) > 0)
+            pArray->Swap( nLo, nHi );
+    }
+    else
+    {
+        SCCOLROW ni = nLo;
+        SCCOLROW nj = nHi;
+        do
+        {
+            while ((ni <= nHi) && (Compare(pArray, pMatSrc, ni, nLo)) < 0)
+                ni++;
+            while ((nj >= nLo) && (Compare(pArray, pMatSrc, nLo, nj)) < 0)
+                nj--;
+            if (ni <= nj)
+            {
+                if (ni != nj)
+                    pArray->Swap( ni, nj );
+                ni++;
+                nj--;
+            }
+        } while (ni < nj);
+        if ((nj - nLo) < (nHi - ni))
+        {
+            if (nLo < nj)
+                QuickSort(pArray, pMatSrc, nLo, nj);
+            if (ni < nHi)
+                QuickSort(pArray, pMatSrc, ni, nHi);
+        }
+        else
+        {
+            if (ni < nHi)
+                QuickSort(pArray, pMatSrc, ni, nHi);
+            if (nLo < nj)
+                QuickSort(pArray, pMatSrc, nLo, nj);
+        }
+    }
+}
+
+short ScInterpreter::Compare( ScSortInfoArray* pArray, const ScMatrixRef& pMatSrc, SCCOLROW nIndex1, SCCOLROW nIndex2 ) const
+{
+    short nRes;
+    sal_uInt16 nSort = 0;
+    do
+    {
+        ScSortInfo& rInfo1 = pArray->Get( nSort, nIndex1 );
+        ScSortInfo& rInfo2 = pArray->Get( nSort, nIndex2 );
+        if (!pMatSrc)
+        {
+            if (aSortParam.bByRow)
+                nRes = CompareCell( nSort, rInfo1.maCell, rInfo2.maCell );
+            else
+                nRes = CompareCell( nSort, rInfo1.maCell, rInfo2.maCell );
+        }
+        else
+        {
+            if (aSortParam.bByRow)
+                nRes = CompareMatrixCell( pMatSrc, nSort,
+                    static_cast<SCCOL>(aSortParam.maKeyState[nSort].nField), rInfo1.nOrg,
+                    static_cast<SCCOL>(aSortParam.maKeyState[nSort].nField), rInfo2.nOrg );
+            else
+                nRes = CompareMatrixCell( pMatSrc, nSort,
+                    static_cast<SCCOL>(rInfo1.nOrg), aSortParam.maKeyState[nSort].nField,
+                    static_cast<SCCOL>(rInfo2.nOrg), aSortParam.maKeyState[nSort].nField );
+        }
+    } while ( nRes == 0 && ++nSort < pArray->GetUsedSorts() );
+    if( nRes == 0 )
+    {
+        ScSortInfo& rInfo1 = pArray->Get( 0, nIndex1 );
+        ScSortInfo& rInfo2 = pArray->Get( 0, nIndex2 );
+        if( rInfo1.nOrg < rInfo2.nOrg )
+            nRes = -1;
+        else if( rInfo1.nOrg > rInfo2.nOrg )
+            nRes = 1;
+    }
+    return nRes;
+}
+
+short ScInterpreter::CompareCell( sal_uInt16 nSort, ScRefCellValue& rCell1, ScRefCellValue& rCell2 ) const
+{
+    short nRes = 0;
+
+    CellType eType1 = rCell1.getType(), eType2 = rCell2.getType();
+
+    if (!rCell1.isEmpty())
+    {
+        if (!rCell2.isEmpty())
+        {
+            bool bErr1 = false;
+            bool bStr1 = ( eType1 != CELLTYPE_VALUE );
+            if (eType1 == CELLTYPE_FORMULA)
+            {
+                if (rCell1.getFormula()->GetErrCode() != FormulaError::NONE)
+                {
+                    bErr1 = true;
+                    bStr1 = false;
+                }
+                else if (rCell1.getFormula()->IsValue())
+                {
+                    bStr1 = false;
+                }
+            }
+
+            bool bErr2 = false;
+            bool bStr2 = ( eType2 != CELLTYPE_VALUE );
+            if (eType2 == CELLTYPE_FORMULA)
+            {
+                if (rCell2.getFormula()->GetErrCode() != FormulaError::NONE)
+                {
+                    bErr2 = true;
+                    bStr2 = false;
+                }
+                else if (rCell2.getFormula()->IsValue())
+                {
+                    bStr2 = false;
+                }
+            }
+
+            if ( bStr1 && bStr2 )           // only compare strings as strings!
+            {
+                OUString aStr1 = rCell1.getSharedString()->getString();
+                OUString aStr2 = rCell2.getSharedString()->getString();
+
+                CollatorWrapper& rSortCollator = ScGlobal::GetCollator(aSortParam.bCaseSens);
+                nRes = static_cast<short>( rSortCollator.compareString( aStr1, aStr2 ) );
+            }
+            else if ( bStr1 )               // String <-> Number or Error
+            {
+                if (bErr2)
+                    nRes = -1;              // String in front of Error
+                else
+                    nRes = 1;               // Number in front of String
+            }
+            else if ( bStr2 )               // Number or Error <-> String
+            {
+                if (bErr1)
+                    nRes = 1;               // String in front of Error
+                else
+                    nRes = -1;              // Number in front of String
+            }
+            else if (bErr1 && bErr2)
+            {
+                // nothing, two Errors are equal
+            }
+            else if (bErr1)                 // Error <-> Number
+            {
+                nRes = 1;                   // Number in front of Error
+            }
+            else if (bErr2)                 // Number <-> Error
+            {
+                nRes = -1;                  // Number in front of Error
+            }
+            else                            // Mixed numbers
+            {
+                double nVal1 = rCell1.getValue();
+                double nVal2 = rCell2.getValue();
+                if (nVal1 < nVal2)
+                    nRes = -1;
+                else if (nVal1 > nVal2)
+                    nRes = 1;
+            }
+            if ( !aSortParam.maKeyState[nSort].bAscending )
+                nRes = -nRes;
+        }
+        else
+            nRes = -1;
+    }
+    else
+    {
+        if (!rCell2.isEmpty())
+            nRes = 1;
+        else
+            nRes = 0;                   // both empty
+    }
+    return nRes;
+}
+
+short ScInterpreter::CompareMatrixCell( const ScMatrixRef& pMatSrc, sal_uInt16 nSort, SCCOL nCell1Col, SCROW nCell1Row,
+    SCCOL nCell2Col, SCROW nCell2Row ) const
+{
+    short nRes = 0;
+
+    // 1st value
+    bool bCell1Empty = false;
+    bool bCell1Value = false;
+    if (pMatSrc->IsEmpty(nCell1Col, nCell1Row))
+        bCell1Empty = true;
+    else if (pMatSrc->IsStringOrEmpty(nCell1Col, nCell1Row))
+        bCell1Value = false;
+    else
+        bCell1Value = true;
+
+    // 2nd value
+    bool bCell2Empty = false;
+    bool bCell2Value = false;
+    if (pMatSrc->IsEmpty(nCell2Col, nCell2Row))
+        bCell2Empty = true;
+    else if (pMatSrc->IsStringOrEmpty(nCell2Col, nCell2Row))
+        bCell2Value = false;
+    else
+        bCell2Value = true;
+
+    if (!bCell1Empty)
+    {
+        if (!bCell2Empty)
+        {
+            if ( !bCell1Value && !bCell2Value )           // only compare strings as strings!
+            {
+                OUString aStr1 = pMatSrc->GetString(nCell1Col, nCell1Row).getString();
+                OUString aStr2 = pMatSrc->GetString(nCell2Col, nCell2Row).getString();
+
+                CollatorWrapper& rSortCollator = ScGlobal::GetCollator(aSortParam.bCaseSens);
+                nRes = static_cast<short>( rSortCollator.compareString( aStr1, aStr2 ) );
+            }
+            else if ( !bCell1Value )        // String <-> Number or Error
+            {
+                nRes = 1;                   // Number in front of String
+            }
+            else if ( !bCell2Value )        // Number or Error <-> String
+            {
+                nRes = -1;                  // Number in front of String
+            }
+            else                            // Mixed numbers
+            {
+                double nVal1 = pMatSrc->GetDouble(nCell1Col, nCell1Row);
+                double nVal2 = pMatSrc->GetDouble(nCell2Col, nCell2Row);
+                if (nVal1 < nVal2)
+                    nRes = -1;
+                else if (nVal1 > nVal2)
+                    nRes = 1;
+            }
+            if ( !aSortParam.maKeyState[nSort].bAscending )
+                nRes = -nRes;
+        }
+        else
+            nRes = -1;
+    }
+    else
+    {
+        if (!bCell2Empty)
+            nRes = 1;
+        else
+            nRes = 0;                   // both empty
+    }
+    return nRes;
+}
+
 void ScInterpreter::GetSortArray( sal_uInt8 nParamCount, vector<double>& rSortArray, vector<tools::Long>* pIndexOrder, bool bConvertTextInArray, bool bAllowEmptyArray )
 {
     GetNumberSequenceArray( nParamCount, rSortArray, bConvertTextInArray );
diff --git a/sc/source/core/tool/interpr4.cxx b/sc/source/core/tool/interpr4.cxx
index 492ef24bda22..c9e795176297 100644
--- a/sc/source/core/tool/interpr4.cxx
+++ b/sc/source/core/tool/interpr4.cxx
@@ -4128,6 +4128,7 @@ StackVar ScInterpreter::Interpret()
                 case ocRandomNV         : ScRandom();                   break;
                 case ocRandbetweenNV    : ScRandbetween();              break;
                 case ocFilter           : ScFilter();                   break;
+                case ocSort             : ScSort();                     break;
                 case ocTrue             : ScTrue();                     break;
                 case ocFalse            : ScFalse();                    break;
                 case ocGetActDate       : ScGetActDate();               break;
diff --git a/sc/source/core/tool/parclass.cxx b/sc/source/core/tool/parclass.cxx
index a123762cc6cd..0bc87183ad89 100644
--- a/sc/source/core/tool/parclass.cxx
+++ b/sc/source/core/tool/parclass.cxx
@@ -234,6 +234,7 @@ const ScParameterClassification::RawData ScParameterClassification::pRawData[] =
     { ocSkewp,           {{ Reference                                            }, 1, Value }},
     { ocSlope,           {{ ForceArray, ForceArray                               }, 0, Value }},
     { ocSmall,           {{ Reference, Value                                     }, 0, Value }},
+    { ocSort,            {{ ReferenceOrRefArray, ForceArray, ForceArray, Value   }, 0, ForceArrayReturn }},
     { ocStDev,           {{ Reference                                            }, 1, Value }},
     { ocStDevA,          {{ Reference                                            }, 1, Value }},
     { ocStDevP,          {{ Reference                                            }, 1, Value }},
diff --git a/sc/source/core/tool/token.cxx b/sc/source/core/tool/token.cxx
index aefd7a350478..b81cb8bb3d26 100644
--- a/sc/source/core/tool/token.cxx
+++ b/sc/source/core/tool/token.cxx
@@ -1390,6 +1390,7 @@ void ScTokenArray::CheckToken( const FormulaToken& r )
             case ocXLookup:
             case ocXMatch:
             case ocFilter:
+            case ocSort:
             case ocSLN:
             case ocIRR:
             case ocMIRR:
diff --git a/sc/source/filter/excel/xlformula.cxx b/sc/source/filter/excel/xlformula.cxx
index bf32fde22f2d..00b5843ad421 100644
--- a/sc/source/filter/excel/xlformula.cxx
+++ b/sc/source/filter/excel/xlformula.cxx
@@ -603,7 +603,8 @@ const XclFunctionInfo saFuncTable_2021[] =
 {
     EXC_FUNCENTRY_V_VR(  ocXLookup,    3,  6,  0,  "XLOOKUP" ),
     EXC_FUNCENTRY_V_VR(  ocXMatch,     2,  4,  0,  "XMATCH" ),
-    EXC_FUNCENTRY_V_VR(  ocFilter,     2,  3,  0,  "FILTER" )
+    EXC_FUNCENTRY_V_VR(  ocFilter,     2,  3,  0,  "FILTER" ),
+    EXC_FUNCENTRY_V_VR(  ocSort,       1,  4,  0,  "SORT" )
 };
 
 
diff --git a/sc/source/filter/oox/formulabase.cxx b/sc/source/filter/oox/formulabase.cxx
index 59bfc8cf3281..a07edc25efbc 100644
--- a/sc/source/filter/oox/formulabase.cxx
+++ b/sc/source/filter/oox/formulabase.cxx
@@ -877,7 +877,8 @@ const FunctionData saFuncTable2021[] =
 {
     { "COM.MICROSOFT.XLOOKUP",             "XLOOKUP",             NOID,   NOID,   3,  6,  R, { VR, VA, VR }, FuncFlags::MACROCALL_NEW },
     { "COM.MICROSOFT.XMATCH",              "XMATCH",              NOID,   NOID,   2,  4,  V, { VR, VA }, FuncFlags::MACROCALL_NEW },
-    { "COM.MICROSOFT.FILTER",              "FILTER",              NOID,   NOID,   2,  3,  A, { VR, VA }, FuncFlags::MACROCALL_NEW }
+    { "COM.MICROSOFT.FILTER",              "FILTER",              NOID,   NOID,   2,  3,  A, { VR, VA }, FuncFlags::MACROCALL_NEW },
+    { "COM.MICROSOFT.SORT",                "SORT",                NOID,   NOID,   1,  4,  A, { VO }, FuncFlags::MACROCALL_NEW }
 };