1 /* ----------------------------------------------------------------------
2 * Project: CMSIS DSP Library
3 * Title: arm_merge_sort_f32.c
4 * Description: Floating point merge sort
5 *
6 * $Date: 23 April 2021
7 * $Revision: V1.9.0
8 *
9 * Target Processor: Cortex-M and Cortex-A cores
10 * -------------------------------------------------------------------- */
11 /*
12 * Copyright (C) 2010-2021 ARM Limited or its affiliates. All rights reserved.
13 *
14 * SPDX-License-Identifier: Apache-2.0
15 *
16 * Licensed under the Apache License, Version 2.0 (the License); you may
17 * not use this file except in compliance with the License.
18 * You may obtain a copy of the License at
19 *
20 * www.apache.org/licenses/LICENSE-2.0
21 *
22 * Unless required by applicable law or agreed to in writing, software
23 * distributed under the License is distributed on an AS IS BASIS, WITHOUT
24 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
25 * See the License for the specific language governing permissions and
26 * limitations under the License.
27 */
28
29 #include "dsp/support_functions.h"
30 #include "arm_sorting.h"
31
32
topDownMerge(float32_t * pA,uint32_t begin,uint32_t middle,uint32_t end,float32_t * pB,uint8_t dir)33 static void topDownMerge(float32_t * pA, uint32_t begin, uint32_t middle, uint32_t end, float32_t * pB, uint8_t dir)
34 {
35 /* Left array is pA[begin:middle-1]
36 * Right Array is pA[middle:end-1]
37 * They are merged in pB
38 */
39
40 uint32_t i = begin;
41 uint32_t j = middle;
42 uint32_t k;
43
44 // Read all the elements in the sublist
45 for (k = begin; k < end; k++)
46 {
47 // Merge
48 if (i < middle && (j >= end || dir==(pA[i] <= pA[j])) )
49 {
50 pB[k] = pA[i];
51 i++;
52 }
53 else
54 {
55 pB[k] = pA[j];
56 j++;
57 }
58 }
59 }
60
arm_merge_sort_core_f32(float32_t * pB,uint32_t begin,uint32_t end,float32_t * pA,uint8_t dir)61 static void arm_merge_sort_core_f32(float32_t * pB, uint32_t begin, uint32_t end, float32_t * pA, uint8_t dir)
62 {
63 if((int32_t)end - (int32_t)begin >= 2 ) // If run size != 1 divide
64 {
65 int32_t middle = (end + begin) / 2; // Take the middle point
66
67 arm_merge_sort_core_f32(pA, begin, middle, pB, dir); // Sort the left part
68 arm_merge_sort_core_f32(pA, middle, end, pB, dir); // Sort the right part
69
70 topDownMerge(pB, begin, middle, end, pA, dir);
71 }
72 }
73
74
75 /**
76 @ingroup groupSupport
77 */
78
79 /**
80 @addtogroup Sorting
81 @{
82 */
83
84 /**
85 * @param[in] S points to an instance of the sorting structure.
86 * @param[in] pSrc points to the block of input data.
87 * @param[out] pDst points to the block of output data
88 * @param[in] blockSize number of samples to process.
89 *
90 * @par Algorithm
91 * The merge sort algorithm is a comparison algorithm that
92 * divide the input array in sublists and merge them to produce
93 * longer sorted sublists until there is only one list remaining.
94 *
95 * @par A work array is always needed. It must be allocated by the user
96 * linked to the instance at initialization time.
97 *
98 * @par It's an in-place algorithm. In order to obtain an out-of-place
99 * function, a memcpy of the source vector is performed
100 */
101
102
arm_merge_sort_f32(const arm_merge_sort_instance_f32 * S,float32_t * pSrc,float32_t * pDst,uint32_t blockSize)103 void arm_merge_sort_f32(
104 const arm_merge_sort_instance_f32 * S,
105 float32_t *pSrc,
106 float32_t *pDst,
107 uint32_t blockSize)
108 {
109 float32_t * pA;
110
111 /* Out-of-place */
112 if(pSrc != pDst)
113 {
114 memcpy(pDst, pSrc, blockSize*sizeof(float32_t));
115 pA = pDst;
116 }
117 else
118 pA = pSrc;
119
120 /* A working buffer is needed */
121 memcpy(S->buffer, pSrc, blockSize*sizeof(float32_t));
122
123 arm_merge_sort_core_f32(S->buffer, 0, blockSize, pA, S->dir);
124 }
125 /**
126 @} end of Sorting group
127 */
128
