1 files changed, 117 insertions, 0 deletions
diff --git a/MdePkg/Library/BaseLib/QuickSort.c b/MdePkg/Library/BaseLib/QuickSort.c
new file mode 100644
index 000000000000..72dcbaf0ea48
--- /dev/null
+++ b/MdePkg/Library/BaseLib/QuickSort.c
@@ -0,0 +1,117 @@
+/** @file
+  Math worker functions.
+
+  Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>
+  SPDX-License-Identifier: BSD-2-Clause-Patent
+
+**/
+
+#include "BaseLibInternals.h"
+
+/**
+  This function is identical to perform QuickSort,
+  except that is uses the pre-allocated buffer so the in place sorting does not need to
+  allocate and free buffers constantly.
+
+  Each element must be equal sized.
+
+  if BufferToSort is NULL, then ASSERT.
+  if CompareFunction is NULL, then ASSERT.
+  if BufferOneElement is NULL, then ASSERT.
+  if ElementSize is < 1, then ASSERT.
+
+  if Count is < 2 then perform no action.
+
+  @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements
+                                 on return a buffer of sorted elements
+  @param[in] Count               the number of elements in the buffer to sort
+  @param[in] ElementSize         Size of an element in bytes
+  @param[in] CompareFunction     The function to call to perform the comparison
+                                 of any 2 elements
+  @param[out] BufferOneElement   Caller provided buffer whose size equals to ElementSize.
+                                 It's used by QuickSort() for swapping in sorting.
+**/
+VOID
+EFIAPI
+QuickSort (
+  IN OUT VOID                 *BufferToSort,
+  IN CONST UINTN              Count,
+  IN CONST UINTN              ElementSize,
+  IN       BASE_SORT_COMPARE  CompareFunction,
+  OUT VOID                    *BufferOneElement
+  )
+{
+  VOID   *Pivot;
+  UINTN  LoopCount;
+  UINTN  NextSwapLocation;
+
+  ASSERT (BufferToSort     != NULL);
+  ASSERT (CompareFunction  != NULL);
+  ASSERT (BufferOneElement != NULL);
+  ASSERT (ElementSize      >= 1);
+
+  if (Count < 2) {
+    return;
+  }
+
+  NextSwapLocation = 0;
+
+  //
+  // pick a pivot (we choose last element)
+  //
+  Pivot = ((UINT8 *)BufferToSort + ((Count - 1) * ElementSize));
+
+  //
+  // Now get the pivot such that all on "left" are below it
+  // and everything "right" are above it
+  //
+  for (LoopCount = 0; LoopCount < Count -1; LoopCount++) {
+    //
+    // if the element is less than or equal to the pivot
+    //
+    if (CompareFunction ((VOID *)((UINT8 *)BufferToSort + ((LoopCount) * ElementSize)), Pivot) <= 0) {
+      //
+      // swap
+      //
+      CopyMem (BufferOneElement, (UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), ElementSize);
+      CopyMem ((UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), (UINT8 *)BufferToSort + ((LoopCount) * ElementSize), ElementSize);
+      CopyMem ((UINT8 *)BufferToSort + ((LoopCount)*ElementSize), BufferOneElement, ElementSize);
+
+      //
+      // increment NextSwapLocation
+      //
+      NextSwapLocation++;
+    }
+  }
+
+  //
+  // swap pivot to it's final position (NextSwapLocation)
+  //
+  CopyMem (BufferOneElement, Pivot, ElementSize);
+  CopyMem (Pivot, (UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), ElementSize);
+  CopyMem ((UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), BufferOneElement, ElementSize);
+
+  //
+  // Now recurse on 2 partial lists.  neither of these will have the 'pivot' element
+  // IE list is sorted left half, pivot element, sorted right half...
+  //
+  if (NextSwapLocation >= 2) {
+    QuickSort (
+      BufferToSort,
+      NextSwapLocation,
+      ElementSize,
+      CompareFunction,
+      BufferOneElement
+      );
+  }
+
+  if ((Count - NextSwapLocation - 1) >= 2) {
+    QuickSort (
+      (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,
+      Count - NextSwapLocation - 1,
+      ElementSize,
+      CompareFunction,
+      BufferOneElement
+      );
+  }
+}